Implement Fibonacci with memoization in Python. What problem does memoization solve, and what is the time complexity before and after?

How to think about it

What the interviewer is really testing

This question checks three things at once: do you know why naive recursion is slow, can you apply a decorator correctly, and can you compare time complexities? The best answers also mention the iterative bottom-up approach as the space-optimal alternative.

Why naive recursion is so slow

The call tree for fib(5) looks like this — every branch marked with * is a redundant recomputation:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)  *
│   │   └── fib(1)
│   └── fib(2)      *
└── fib(3)           *
    ├── fib(2)       *
    └── fib(1)

fib(40) makes over 300 million calls. The time complexity is O(2^n) because every call branches into two, and subproblems are recalculated from scratch at every level.

The fix — cache results so each n is computed exactly once

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

lru_cache stores (n,) -> result in a dictionary. The first time fib(38) is called, the result is cached. Every subsequent call for fib(38) returns the cached value instantly. Each unique n is now computed exactly once: O(n) time, O(n) space.

Runnable playground — compare all three approaches

Bottom-up DP — the space-optimal approach

def fib(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

This avoids the call stack entirely, handles any n without a recursion limit, and uses O(1) space. It is the right answer when n could be very large.

Comparing all approaches

Approach	Time	Space	Recursion limit?
Naive recursion	O(2^n)	O(n) stack	Yes
lru_cache recursion	O(n)	O(n)	Yes
Manual dict cache	O(n)	O(n)	Yes
Bottom-up iterative	O(n)	O(1)	No