Time complexity of memoized Fibonacci fib(n)?

Options

1. O(2ⁿ)
2. O(n) (Correct option)
3. O(log n)
4. O(n²)

Answer

O(n)

Why

Naive recursive fib calls fib(n-1) and fib(n-2), which call the same values again and again: about 2ⁿ calls.

With memoization, each fib(k) is computed once and then read from a cache. There are only n different values, so O(n).

from functools import lru_cache

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

Remember

Memoization turns repeated work into one-time work.

Key terms

• Memoization
• Dynamic programming
• Big-O notation
• Time complexity
• functools.lru_cache