juniorFibonacci Series

What is the time complexity of the naive recursive Fibonacci?

Updated Apr 28, 2026

Short answer

The time complexity of the naive recursive Fibonacci algorithm is O(2^n) because each function call creates two more recursive calls until reaching the base cases. This causes the same Fibonacci values to be calculated repeatedly, leading to exponential growth in the number of operations. Although the code is simple and matches the mathematical definition, it becomes very slow for large values of n.

Deep explanation

The naive recursive Fibonacci implementation directly follows the Fibonacci recurrence:

TEXT
F(n) = F(n - 1) + F(n - 2)

A typical implementation:

Python
def fibonacci(n):
    if n <= 1:
        return n


    return fibonacci(n - 1) + fibonacci(n - 2)

For every value greater than 1, the function makes two recursive calls:

TEXT
fibonacci(n - 1)
fibonacci(n - 2)

This creates a branching tree of function calls.

Recursive Call Tree

For example:

Python
fibonacci(5)

creates:

TEXT
fib(5)
                       /        \
                   fib(4)       fib(3)
                  /     \       /     \
              fib(3)   fib(2) fib(2) fib(1)
              /   \     /  \
          fib(2) fib(1) ... ...

The same values are computed multiple times:

  • fib(3) is calculated more than once.
  • fib(2) is calculated several times.
  • Smaller Fibonacci values are repeatedly recomputed.

This repeated work is the main reason the algorithm is inefficient.

Time Complexity Derivation

Let T(n) represent the number of operations needed to calculate fib(n).

The recurrence is:

TEXT
T(n) = T(n - 1) + T(n - 2) + O(1)

The function makes two smaller calls and performs a constant amount of extra work to add the results.

The recursion tree grows approximately like:

TEXT
n
          /   \
       n-1     n-2
      /  \     /  \
   n-2  n-3 n-3 n-4

Because each level branches into more calls, the total number of calls grows exponentially.

Therefore:

TEXT
Time Complexity: O(2^n)

Why It Is Not Exactly 2^n

O(2^n) is a simplified upper-bound description. The exact growth rate is closer to the Fibonacci sequence itself:

TEXT
O(φ^n)

where φ (the golden ratio) is approximately:

TEXT
1.618

However, in coding interviews, the expected answer is usually:

TEXT
O(2^n)

because it clearly communicates exponential growth.

Space Complexity

The space complexity is different from the time complexity.

Even though the function creates many calls overall, only one recursive path exists at a time.

Example:

TEXT
fib(5)
 |
fib(4)
 |
fib(3)
 |
fib(2)
 |
fib(1)

The maximum recursion depth is n.

Therefore:

TEXT
Space Complexity: O(n)

Improving the Algorithm

The problem with naive recursion is repeated computation. We can improve it using memoization:

Python
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]


    if n <= 1:
        return n


    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)


    return memo[n]

Each Fibonacci number is calculated only once.

Complexity becomes:

TEXT
Time Complexity: O(n)
Space Complexity: O(n)

An iterative solution can reduce space further:

Python
def fibonacci(n):
    if n <= 1:
        return n


    a, b = 0, 1


    for _ in range(2, n + 1):
        a, b = b, a + b


    return b

Complexity:

TEXT
Time Complexity: O(n)
Space Complexity: O(1)

Real-world example

Suppose a program calculates a Fibonacci value for a simulation:

Python
def fibonacci(n):
    if n <= 1:
        return n


    return fibonacci(n - 1) + fibonacci(n - 2)




print(fibonacci(35))

For a small input like 5, this finishes quickly.

For a larger input like 35, the function performs millions of repeated calculations because it recalculates the same smaller Fibonacci values many times.

A more efficient version:

Python
def fibonacci(n):
    if n <= 1:
        return n


    previous, current = 0, 1


    for _ in range(n):
        previous, current = current, previous + current


    return previous




print(fibonacci(35))

This performs only a linear number of steps.

Common mistakes

  • * Saying the naive recursive Fibonacci algorithm has `O(n)` time complexity.
  • * Confusing recursion depth with the total number of recursive calls.
  • * Forgetting that repeated calculations are the cause of inefficiency.
  • * Assuming a shorter recursive implementation is automatically faster.
  • * Saying the space complexity is `O(2^n)` because there are many function calls over time.
  • * Ignoring the possibility of memoization or iterative optimization.
  • * Using the exact mathematical growth rate when the interview expects the simpler `O(2^n)` explanation.

Follow-up questions

  • Why does naive recursive Fibonacci repeat calculations?
  • What is the space complexity of naive recursive Fibonacci?
  • How can memoization improve Fibonacci time complexity?
  • Why is iterative Fibonacci better than naive recursion?
  • Can Fibonacci be calculated faster than O(n)?
  • How would you explain the inefficiency of recursive Fibonacci in an interview?

More Fibonacci Series interview questions

View all →