What the real Time complexity of Fibonacci recursion function

Question

I am confused about whether the complexity of the Fibonacci function function is 2^n or the golden ratio raised to power n.

"I have noticed that many websites state that the complexity of this recursion is 2 to the power of n."

Answer 1

Let's take this pseudocode to calculate

function F(n):
    if n < 2:
        return n  ' F(0) = 0, F(1) = 1
    return F(n-1) + F(n-2)

Let's call the number of elementary operations (of O(1) complexity) needed to calculate .

Then we have constants and such that:

• ₀ =
• ₁ =
• = ₋₁ + ₋₂ +

Here we take addition as a constant time operation, included in .

We can see this sequence:

• ₂ = 2 + = 2(+) −
• ₃ = 3 + 2 = 3(+) −
• ₄ = 5 + 4 = 5(+) −
• ...
• = ₊₁(+) − = θ(₊₁)

As = θ(φ), we have that:

= θ(φ⁺¹) = θ(φ)

With Big O we cannot get an equivalent expression by changing the base of an exponentiation. Wikipedia on Big O notation warns about this:

On the other hand, exponentials with different bases are not of the same order. For example, 2 and 3 are not of the same order.

And so we cannot say = θ(2), because φ is not 2, but 1.618...

On the other hand, since in theory big O gives an upper bound, we can actually say that = O(2), but it is not a precise bound. More precise is using big Omega so to identify a tight bound.

In conclusion we have these truths:

• = θ(φ)
• = O(2)

But:

• ≠ θ(2)