O(2ⁿ) Exponential Time | Big-O Learning

🎯 HOOK

The Chain Letter Problem

You receive a chain letter that says "send this to 2 friends." If everyone follows the rule, how many people receive the letter after 10 generations?

🧪 EXPLORE

Visualize Recursive Fibonacci

Watch how computing Fibonacci recursively creates an explosion of function calls!

Compute fib(5)

⚠️ Values above 8 will take a while!

Function Calls

0

Expected (2ⁿ)

32

Result

-

⚠️ Critical: Notice how adding just +1 to n roughly doubles the work! This is why O(2ⁿ) becomes impossible for large n.

💡 EXPLAIN

What is O(2ⁿ)?

Exponential time means each increment of n roughly doubles the work.

💥

Think of it like branching explosively

✓ Naive recursive Fibonacci
✓ Generating all subsets of a set
✓ Solving puzzles by trying all possibilities (brute force)
✓ Tower of Hanoi

# Simple recursive Fibonacci (O(2ⁿ))

def fibonacci(n):

if n <= 1:

return n

return fibonacci(n - 1) + fibonacci(n - 2)

# Optimized with memoization (O(n))

def fibonacci_fast(n, memo={}):

if n in memo:

return memo[n]

if n <= 1:

return n

memo[n] = fibonacci_fast(n-1, memo) + fibonacci_fast(n-2, memo)

return memo[n]

🚨 Why O(2ⁿ) is Catastrophic:

• n=10: ~1,000 steps (1 second)
• n=20: ~1,000,000 steps (17 minutes)
• n=30: ~1,000,000,000 steps (12 days!)
• n=40: ~1 trillion steps (31 years!!)

How to Avoid O(2ⁿ)

• Use memoization/caching
• Dynamic programming
• Look for mathematical shortcuts
• Use iterative solutions

When O(2ⁿ) is Acceptable

• Very small n (n ≤ 15)
• No better program exists
• Prototype/toy problems
• When correctness > speed

✏️ PRACTICE

Test Your Understanding

1. Which is O(2ⁿ)?

2. Recursive fib(10) takes 1 second. Roughly how long for fib(15)?

3. How can you optimize recursive Fibonacci?

4. True or False: O(2ⁿ) is always the worst speed

5. What's the practical limit for O(2ⁿ) algorithms?

6. Real-world: Password cracking

A 10-character password using 62 possible characters (a-z, A-Z, 0-9). What's the speed to try all combinations?

🤔 REFLECT