Fibonacci (DP)

dynamic programming · O(n)

5

Configure inputs and press Visualize to begin.

Press Visualize
Pseudocode & Implementations
3 approaches

Naive recursion recomputes sub-problems exponentially. F(50) makes ~10¹⁰ calls.

FIB-NAIVE(n):
  IF n <= 1: RETURN n
  RETURN FIB-NAIVE(n-1) + FIB-NAIVE(n-2)
Complexity Analysis

Time Complexity

Best Case
LinearO(n)
Average
LinearO(n)
Worst Case
LinearO(n)
Space (aux)
LinearO(n)
dpmemoizationclassic
About

Computes Fibonacci numbers bottom-up, building a table from base cases. Eliminates exponential recursion.

Key Insight

Transforms O(2ⁿ) naive recursion to O(n) by storing subproblem solutions — the essence of DP.

Use Cases

Classic DP introductionUnderstanding memoization