The Concept

Computing the N-th Fibonacci number recursively takes exponential time $O(2^N)$ because we solve the exact same subproblems repeatedly. Dynamic Programming solves this using Memoization:

  • We pass a hash map or array (memo) to store the results of subproblems.
  • Before solving a subproblem, we check if it is already in our memo.
  • If yes, we return it instantly in $O(1)$ time.
  • If no, we compute it and store it in memo for future queries.

Code Implementation

Below is the recursive memoization implementation of Fibonacci:

Loading...
  • Time Complexity: $O(N)$ because we compute each Fibonacci state exactly once.
  • Space Complexity: $O(N)$ for the memoization cache and call stack.

Interactive Lab: Fibonacci Memoization

Observe the recursion tree pruned in real-time. Try changing the input size and see how memo lookups skip branch executions:

Key Insight

Memoization turns an exponential $O(2^N)$ runtime into a linear $O(N)$ runtime by trading space for speed. For large values of $N$, this optimization makes the difference between a system crash and an instant return.