Introduction

Fibonacci is a classic complexity example because the same mathematical sequence can be computed with wildly different runtime behavior. A correct Big-O answer should discuss both time and space complexity and should distinguish between the algorithmic idea and the details of the implementation.

Naive Recursion Is Exponential

The textbook recursive definition is elegant but slow because it recomputes the same subproblems many times.

1def fib_recursive(n: int) -> int:
2    if n < 2:
3        return n
4    return fib_recursive(n - 1) + fib_recursive(n - 2)

This implementation has:

• time complexity around O(phi^n), often loosely written as O(2^n)
• space complexity O(n) from recursion depth

The key reason is repeated work. fib_recursive(40) ends up recalculating many smaller Fibonacci values over and over again.

Memoization Reduces It to Linear Time

If you cache previously computed results, each fib(k) is solved once.

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def fib_memo(n: int) -> int:
5    if n < 2:
6        return n
7    return fib_memo(n - 1) + fib_memo(n - 2)

Now the complexity becomes:

• time O(n)
• space O(n) for the cache and recursion stack

This is a dramatic improvement while keeping the recursive structure.

Iterative Dynamic Programming Is Linear Time and Constant Extra Space

A bottom-up iterative version avoids both repeated work and deep recursion.

1def fib_iterative(n: int) -> int:
2    if n < 2:
3        return n
4
5    a, b = 0, 1
6    for _ in range(2, n + 1):
7        a, b = b, a + b
8    return b

This has:

• time O(n)
• extra space O(1)

For many practical input sizes, this is the most sensible implementation because it is simple, fast, and avoids recursion overhead.

Fast Doubling Gives Logarithmic Time

There are also O(log n) methods. Fast doubling is one of the cleanest.

1def fib_fast(n: int) -> int:
2    def helper(k: int):
3        if k == 0:
4            return (0, 1)
5
6        a, b = helper(k // 2)
7        c = a * (2 * b - a)
8        d = a * a + b * b
9
10        if k % 2 == 0:
11            return (c, d)
12        return (d, c + d)
13
14    return helper(n)[0]

This approach has:

• time O(log n)
• space O(log n) because of recursion depth

Matrix exponentiation achieves the same asymptotic time complexity and is useful when you generalize beyond Fibonacci to other linear recurrences.

Asymptotics Are Not the Whole Story

For small n, the simplest linear iterative version may outperform more sophisticated O(log n) techniques because constant factors are smaller. For very large n, the logarithmic methods become more attractive.

There is another subtle point too: Fibonacci numbers grow quickly, so arithmetic on very large integers is itself expensive. Eventually, big-integer multiplication costs start to matter, which means raw Big-O in terms of n is only part of the performance story.

Another subtle mistake is benchmarking only tiny values of n and then drawing asymptotic conclusions from that data. Small-input measurements mostly show interpreter overhead and constant factors, not the real growth pattern of the algorithm.

Common Pitfalls

Calling naive recursion O(n) ignores repeated subproblem expansion.

Reporting only time complexity and omitting recursion-stack or cache-space costs gives an incomplete answer.

Assuming the asymptotically fastest method is always the practical winner ignores constant factors and implementation overhead.

Summary

• Naive recursion is exponential in time and linear in stack space.
• Memoized recursion and iterative dynamic programming reduce time to O(n).
• Iterative Fibonacci can also achieve O(1) extra space.
• Fast doubling and matrix methods reduce time to O(log n).
• The best implementation depends on both input size and practical overhead, not just asymptotic notation.