[Solved]: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

Problem Detail: 

I learned that recursive Fibonacci is $O(2^N)$.

However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near abouts? It's like less then half!

$COUNT = 0  def fibonacci( n )    $COUNT +=1    return  n  if ( 0..1 ).include? n   # Base Case returns 0 or 1       fibonacci( n - 1 ) + fibonacci( n - 2 ) # Recursive case end 

Asked By : 500

Answered By : Raphael

You ask,

I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?

There are many things wrong in the implied conclusion.

1. $O(\_)$ only gives you an upper bound. The true behaviour may be of much smaller growth.
2. Asymptotics (like $O(\_))$ only give you only something in the limit, that is you can only expect the bound to hold for large $n$.

3. Since you use $O$ as though it was $\Omega$, note that a (lower) bound on runtime does not necessarily translate into a (lower) bound on recursive calls, each of which may take $\omega(1)$ time.

   Similarly, a tight upper runtime bound (which you don't have) may not be a tight upper bound on the number of recursive calls for the same reasons.

You can analyse exactly how many recursive calls you need. Just solve the recurrence

$\qquad\displaystyle \begin{align*} f(0) &= 1,\\ f(1) &= 1,\\ f(n) &= f(n-1) + f(n-2) + 1, \quad n \geq 3, \end{align*}$

which adds up $1$ for every recursive call your program makes. See here for more detail on how you get to such recurrences.

See here how to do that, or use computer algebra. The result is

$\qquad f(n) = 2F_{n+1} - 1$;

insert $n=5$ and you will get $f(n) = 15$. It's not that surprising that the Fibonacci numbers $F_n$ should show up. Inserting their known closed form, we get

$\qquad\displaystyle f(n) = \frac{2}{\sqrt{5}} \cdot \Bigl( \varphi^{n+1} - (1-\varphi)^{n+1} \Bigr) - 1$

with $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.62$ the golden ratio. This closed form of $f(n)$ implies

$\qquad\displaystyle f(n) \sim \frac{2}{\sqrt{5}} \cdot \varphi^{n+1} \approx 1.45 \cdot 1.62^n$

since $0< 1 - \varphi < 1 < \varphi$. We see that the $O(2^n)$-bound is rather loose -- it has exponential absolute and relative error.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44855