Proving this recursive Fibonacci implementation runs in time O(2^n)?

Question

I'm having difficulty proving that the 'bad' version of fibonacci is O(2^n). Ie. Given the function

int fib(int x)
{
  if ( x == 1 || x == 2 )
  {
    return 1;
  }
  else
  {
    return ( f( x - 1 ) + f( x - 2) );
  }
}

Can I get help for the proof of this being O(2^n).

Have you seen this: http://stackoverflow.com/q/7547133/1968462 — Kat, Oct 15 '13 at 23:38
I'm not sure this question is a duplicate of the linked one. The linked one asks specifically to see where a particular line of reasoning breaks down, while this is a more general question about how to prove the upper bound is O(2^n) with no starting assumptions. — templatetypedef, Oct 15 '13 at 23:50

score 6 · Answer 1 · answered Oct 15 '13 at 23:43

Let's start off by writing a recurrence relation for the runtime:

T(1) = 1

T(2) = 1

T(n+2) = T(n) + T(n + 1) + 1

Now, let's take a guess that

T(n) ≤ 2ⁿ

If we try to prove this by induction, the base cases check out:

T(1) = 1 ≤ 2 = 2¹

T(2) = 1 ≤ 4 = 2²

Then, in the inductive step, we see this:

T(n + 2) = T(n) + T(n + 1) + 1

≤ 2ⁿ + 2ⁿ⁺¹ + 1

< 2ⁿ⁺¹ + 2ⁿ⁺¹

= 2ⁿ⁺²

Therefore, by induction, we can conclude that T(n) ≤ 2ⁿ for any n, and therefore T(n) = O(2ⁿ).

With a more precise analysis, you can prove that T(n) = 2F_n - 1, where F_n is the nth Fibonacci number. This proves, more accurately, that T(n) = Θ(φⁿ), where φ is the Golden Ratio, which is approximately 1.61. Note that φⁿ = o(2ⁿ) (using little-o notation), so this is a much better bound.

Hope this helps!

score 0 · Answer 2 · answered Oct 15 '13 at 23:43

0

Try manually doing a few test cases like f(5) and take note of how many times the method f() is called.

A fat hint would be to notice that every time the method f() is called (except for x is 1 or 2), f() is called twice. Each of those call f() two more times each, and so on...

answered Oct 15 '13 at 23:43

Utkash Dubey

13
6

2

While this gives a good intuition, that really isn't a proof. – templatetypedef Oct 15 '13 at 23:44
@templatetypedef -- I know, I didn't think it would be good to just give him a straight answer (it felt too much like something from a basic pset) – Utkash Dubey Oct 16 '13 at 01:15

score 0 · Answer 3 · answered Oct 16 '13 at 11:45

There's actually a pretty simple proof that the total number of calls to the f is going to be 2Fib(n)-1, where Fib(n) is the n'th Fibonacci number. It goes like this:

The set of calls to f form a binary tree, where each call is either a leaf (for x=1 or x=2) or else the call spawns two child calls (for x>2).
Each leaf contributes exactly 1 to the total returned by the original call, therefore there are Fib(n) total leaves.
The total number of internal nodes in any binary tree is equal to L-1, where L is the number of leaves, so the total number of nodes in this tree is 2L-1.

This shows that the running time (measured in terms of total calls to f) is

T(n)=2Fib(n)-1=O(Fib(n))

and since Fib(n)=Θ(φ^n), where φ is the golden ratio

Φ=(1+sqrt{5})/2 = 1.618...

this proves that T(n) = Θ(1.618...^n) = O(n).

score 0 · Answer 4 · answered Oct 17 '13 at 01:09

Using the Recursion Tree Method :

                                             T(n)                         
                                       ↙            ↘
                                   n-1              n – 2                                 
                               ↙      ↘             ↙      ↘
                           N – 2      n – 3      n – 3       n - 4

Each tree level is considered as a call for fib(x - 1) fib(x - 2) if you complete the recursion tree on this manner you will stop when x = 1 or x = 2 (base case) .... this tree shows only three levels of the recursion tree . To solve this tree you need these important informations : 1- height of the tree. 2-how much work is done at each level . The height of this tree is 2^n and the work at each level is O(1) then the Order of this recurrence is Height * Work at each level = 2^n * 1 = O(2^n)

Note that the tree isn't a perfect binary tree. The branch for n - 2 drops off twice as early as the branch for n - 1. That's why this only works out to an upper bound rather than a tight bound. — templatetypedef, Oct 17 '13 at 01:11
@templatetypedef I know ... But proving any recurrence with recursion tree is the simplest way — Ibrahim Amer, Oct 17 '13 at 13:42

Proving this recursive Fibonacci implementation runs in time O(2^n)?

4 Answers4