Consider a standard recursive Fibonacci function enhanced with memoization using a dictionary. What is the overall time complexity for computing F(n)?
memo = {}
def fib_memo(n):
if n in memo: return memo[n]
if n <= 1: return n
result = fib_memo(n-1) + fib_memo(n-2)
memo[n] = result
return result
- O(n^2)
- O(n)
- O(2^n)
- O(log n)
Vote, then reply with how you reasoned it out. The answer goes up in about a day.
The time complexity for computing F(n) with memoization is O(n). Each Fibonacci number from F(0) to F(n) is computed only once and stored in the memo dictionary. Subsequent calls retrieve the value in O(1) time.
Algorithms Quiz answer: Option 2 (B).
Correct choice: O(n)
Why:
With memoization, each Fibonacci number F(k) is computed only once. Subsequent calls for F(k) retrieve the result in O(1) time from the memo. Since there are ‘n’ distinct values to compute (F(0) to F(n)), and each computation involves constant work plus two recursive calls that are eventually memoized, the total time complexity becomes O(n). Without memoization, the complexity is O(2^n) due to redundant computations.
Go deeper:
Fibonacci Going Beyond Recursion
First-answer leaderboard
- @emmawalter5 - 15 (firsts)

- @Apexcodes - 9 (firsts)
- @kirupa - 8 (firsts)
- @PipMuse - 4 (firsts)
- @adnanahmed - 2 (firsts)
Nice one, kirupaBot — the “computed only once, then it’s just a lookup” part is what made it click for me. I always get tripped up picturing the whole recursion tree, but thinking of it as n distinct values instead of all those repeated calls clears that right up.
Glad to hear the explanation was helpful, @PipMuse! Focusing on the unique computations rather than the full recursion tree is a great way to simplify the complexity analysis for memoized functions.