Why is runtime of Fibonacci θ(1.6^N)?

Question

Why is the runtime closer to O(1.6^N) and not O(2^N)? I think it has something to do with the call stack, but it's still a little unclear to me.

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Answer 1

For starters, remember that big-O notation always provides an upper bound. That is, if a function is O(n), it's also O(n²), O(n³), O(2ⁿ), etc. So in that sense, you are not incorrect if you say that the runtime is O(2ⁿ). You just don't have a tight bound.

To see where the tight bound of Θ(φⁿ) comes from, it might help to look at how many recursive calls end up getting made when evaluating Fibonacci(n). Notice that

• Fibonacci(0) requires one call, the call to Fibonacci(0).
• Fibonacci(1) requires one call, the call to Fibonacci(1).
• Fibonacci(2) requires three calls: one to Fibonacci(2), and one each to Fibonacci(0) and Fibonacci(1).
• Fibonacci(3) requires five calls: one to Fibonacci(3), then the three calls generated by invoking Fibonacci(2) and the one call generated by invoking Fibonacci(1).
• Fibonacci(4) requires nine calls: one to Fibonacci(4), then five from the call to Fibonacci(3) and three from the call to Fibonacci(2).

More generally, the pattern seems to be that if you're calling Fibonacci(n) for some n ≥ 2, that the number of calls made is one (for the call itself), plus the number of calls needed to evaluate Fibonacci(n-1) and Fibonacci(n-2). If we let L_n denote the number of calls made, this means that we have that

• L₀ = L₁ = 1
• L_n+2 = 1 + L_n + L_n+1.

So now the question is how fast this sequence grows. Evaluating the first few terms gives us

1, 1, 3, 5, 9, 15, 25, 41, ...

which definitely gets bigger and bigger, but it's not clear how much bigger that is.

Something you might notice here is that L_n kinda sorta ish looks like the Fibonacci numbers. That is, it's defined in terms of the sum of the two previous terms, but it has an extra +1 term. So maybe we might want to look at the difference between L_n and F_n, since that might show us how much "faster" the L series grows. You might notice that the first two values of the L series are 1, 1 and the first two values of the Fibonacci series are 0, 1, so we'll shift things over by one term to make things line up a bit more nicely:

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff:    0   0   1   2   4   7  12  20

And wait, hold on a second. What happens if we add one to each term of the difference? That gives us

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff+1   1   1   2   3   5   8  13  21

Whoa! Looks like L_n - F_n+1 + 1 = F_n+1. Rearranging, we see that

L_n = 2F_n+1 - 1.

Wow! So the actual number of calls made by the Fibonacci recursive function is very closely related to the actual value returned. So we could say that the runtime of the Fibonacci function is Θ(F_n+1) and we'd be correct.

But now the question is where φ comes in. There's a lovely mathematical result called Binet's formula that says that F_n = Θ(φⁿ). There are many ways to prove this, but they all essentially boil down to the observation that

1. the Fibonacci numbers seem to grow exponentially quickly;
2. if they grow exponentially with a base of x, then F_n+2 = F_n + F_n+1 can be rewritten as x² = x + 1; and
3. φ is a solution to x² = x + 1.

From this, we can see that since the runtime of Fibonacci is Θ(F_n+1), then the runtime is also Θ(φⁿ⁺¹) = Θ(φⁿ).