Here is fib(n) again:

Complexity of fib(n), the naive way¶

The call tree will look like:

     1                                                       level
       \                           
      ...       ...             1                            ....  
        ...    ...            ...                              5
         n-2  n-3    n-3    n-4                                4
            \/        \/                                       3
            n-1   _  n-2                                       2
              \ /                                              1
               n                                               0

The longest branch is the leftmost one, and it's of length $n$. The shortest branch is the rightmost one (which goes n, n-2, n-4, ... 1), and it's of length that's approximately $n/2$ (since we are going from n to 1 in steps of 2.)

It's hard to count all the calls, but we can get an upper bound and a lower bound on their number.

To get the upper bound, assume that all the "branches" of the call tree are of length n (the longest one). Here are the numbers of calls we have at each level:

            level 0:       1 call     (2^0)
            level 1:       2 calls    (2^1)
            level 3:       4 calls    (2^2)

            ...                 

            level (n-1):   2^(n-1) calls

So in total we have fewer than $1 + 2 + 4 +... + 2^{n-1} = 2^{n}-1$ calls (i.e. $\mathcal{O}(2^n)$). This is the upper bound on the number of calls.

Now, let's get a lower bound on the number of calls (of course, one lower bound is 0, but let's get an interesting lower bound!). The shorterst branch, which is the rightmost branch, is of length n/2. Using the same analysis, if all the branches were of length $n/2$, we'll have $2^{n/2}-1 = \sqrt(2)^n -1$ calls, i.e., the number of calls is $\mathcal{O}(\sqrt(2)^n)$.

So we have more than $\mathcal{O}(\sqrt(2)^n)$ calls and less than $\mathcal{O}(2^n)$ calls.

But we can do better!

To compute fib(n), we need to compute fib(n-1) and fib(n-2) (and add them and return the result, but that takes almost no time at all).

Suppose it takes $T(n)$ seconds to compute fib(n) (and so $T(n-1)$ for fib(n-1) and $T(n-2)$ for fib(n-2)).

Since the time to compute fib(n) is the time to compute fib(n-1) plus the time to compute fib(n-2), we get, approximately,

$$T(n) \approx T(n-1) + T(n-2)$$

So the time to compute a fib(n) itself looks like fib(n)! That means that the time to compute fib(n) is (again, approximately, since we are ignoring a bit of computation that happens in fib) $\mathcal{O}(fib(n))$.

(Note that it's true that T(0)=T(1)=\text{const}.)

In fact, you can use linear algebra to prove that $fib(n) = \text{round}(\phi^n/\sqrt{5})$, where $\phi$ is the Golden Ratio, $\frac{1+\sqrt{5}}{2}\approx 1.61$.

This means that fib(n) runs in $\mathcal{O}(\phi^n)$ time.

Aside: an approximation for $\phi$¶

We bounded the number of calls made to between $\mathcal{O}(\sqrt(2)^n)$ and $\mathcal{O}(2^n)$ calls. The exact estimate is $\mathcal{O}(\phi^n)$. We actually got a pretty nice estimate for $\phi$ by thinking about the complexity of fib:

$\sqrt{2} < \phi < 2$