# Time complexity of Fibonacci sequence and other recursion

Page 1 of 1

## 4 Replies - 17924 Views - Last Post: 07 October 2012 - 08:06 PM

### #1 byrandomby1

Reputation: 2
• Posts: 124
• Joined: 08-March 11

# Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 03:41 AM

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

```int fib(int n)
{
if (n <= 2) return 1
else return fib(n-1) + fib(n-2)
}
```

How do I differentiate between O(2^n) and O(n^2)?

If there is a recursive function

```int fib(int n)
{
if (n <= 3) return 1
else return fib(n-1) + fib(n-2) + fib(n-3)
}
```

would the time complexity be O(3^n)?

Is This A Good Question/Topic? 0

## Replies To: Time complexity of Fibonacci sequence and other recursion

### #2 macosxnerd101

• Self-Trained Economist

Reputation: 10803
• Posts: 40,257
• Joined: 27-December 08

## Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 11:11 AM

The Fibonacci sequence is O(2^n). You can prove it mathematically. Remember the definition of Big-O: f(n) is O(g(n)) iff there exist constants C and k (positive integers) such that |f(x)| <= C*|g(x)| for all x >= k.

So we know that Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2^n. Now prove inductively that f(n) <= g(n) starting at some x. Then solve for C.

I have a Big-O proofs tutorial you may find helpful.

### #3 sepp2k

• D.I.C Lover

Reputation: 2153
• Posts: 3,311
• Joined: 21-June 11

## Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 11:46 AM

macosxnerd101, on 06 October 2012 - 08:11 PM, said:

The Fibonacci sequence is O(2^n).

Note that this does not automatically imply that the cost of calculating the Fibonacci sequence is also in O(2^n) (and more importantly Theta(2^n)) (and in fact there are many ways of calculating it that are O(n)). So you still need to show that this particular way of calculating the sequence takes a number of steps proportional to fib(n).

### #4 macosxnerd101

• Self-Trained Economist

Reputation: 10803
• Posts: 40,257
• Joined: 27-December 08

## Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 01:18 PM

That's a good point. Actually solving the recurrence relation mathematically would allow you to find the first n Fibonacci numbers in O(n) time. This particular solution is O(2^n).

### #5 mojo666

Reputation: 356
• Posts: 785
• Joined: 27-June 09

## Re: Time complexity of Fibonacci sequence and other recursion

Posted 07 October 2012 - 08:06 PM

Quote

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

The reason the recursive variation is O(2^n) is because it does a lot of redundant calculations. For example, you need to calculate fib(n-1) + fib(n-2). In order to find fib(n-1), you need to calculate fib(n-2)+fib(n-3). So, already all the work that goes into calculating fib(n-2) is done twice. To understand it conceptually, I suggest you pick a few numbers for n and draw out the corresponding recursive calls. You will see that fib(1) and fib(2) get called about O(2^n) times. To show it formally, you should try what Mac suggested.

Quote

How do I differentiate between O(2^n) and O(n^2)?

An easy way to conceptualize 2^n is thinking "if I increase n by one, then I just doubled the runtime." That means if you increase n by 2 then you doubled the already doubled runtime and so on. To conceptualize O(n^2), if you increase n by 1, then you roughly added 2*n units of time to the runtime.

Quote

would the time complexity be O(3^n)?

Yes.