# Time complexity of Fibonacci sequence and other recursion

Page 1 of 1

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

### #1 byrandomby1

• D.I.C Head

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

• Games, Graphs, and Auctions

Reputation: 11335
• Posts: 42,754
• 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.
Was This Post Helpful? 0

### #3 sepp2k

• D.I.C Lover

Reputation: 2270
• Posts: 3,483
• 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).
Was This Post Helpful? 1

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11335
• Posts: 42,754
• 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).
Was This Post Helpful? 0

### #5 mojo666

• D.I.C Addict

Reputation: 378
• Posts: 818
• 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.
Was This Post Helpful? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }