O(2ⁿ): Exponential Time
What you'll learn: You'll understand what exponential time complexity means and why certain recursive algorithms grow explosively slow as input increases.
The Core Idea
Exponential time complexity occurs when an algorithm's runtime doubles (or multiplies by some constant) with each additional element of input. The most common form, O(2ⁿ), means that adding just one more item to your input roughly doubles the number of operations.
This happens frequently in recursive algorithms that make multiple recursive calls at each step, creating a branching tree of computation.
The Classic Example: Naive Fibonacci
Remember the recursive Fibonacci function you learned earlier? It makes two recursive calls:
fib(n) = fib(n-1) + fib(n-2)
Each call spawns two more calls, which each spawn two more, and so on. If you drew this out, you'd see a binary tree of calls:
fib(5)makes 2 calls- Those 2 calls make 4 calls total
- Those 4 make 8 calls
- Those 8 make 16 calls
- And so on...
For fib(10), you're making hundreds of calls. For fib(50), you're making over a quadrillion calls. The growth is catastrophic.
Why It Matters
Exponential algorithms become impractical extremely quickly. Even on the fastest computers:
- n = 20: manageable
- n = 40: takes seconds
- n = 60: might take years
Key Takeaway: O(2ⁿ) represents exponential time complexity where each input increment doubles the work; this appears in recursive algorithms with multiple branches per call, like naive Fibonacci, and becomes impractically slow for even moderate input sizes.