Algorithms Quiz: Hard: Memoized Fibonacci Complexity

programming
1

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)
0 voters

Vote, then reply with how you reasoned it out. The answer goes up in about a day.

2

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.