Exponential Time O(2ⁿ) — When Problems Explode

What Is O(2ⁿ) Exponential Time?

An algorithm is O(2ⁿ) when the number of operations doubles with each additional element in the input. Even modest inputs become computationally infeasible:

Growth Rate

n	2ⁿ
10	1,024
20	1,048,576
30	1,073,741,824
40	~1.1 trillion
50	~1.1 quadrillion

At n = 50, even a computer doing a billion operations per second would need over 13 days.

Why Algorithms Become Exponential

Exponential time usually arises when an algorithm must consider all subsets or all combinations of the input. With n items, there are 2ⁿ possible subsets.

Classic O(2ⁿ) Problems

1. Naive Fibonacci recursion — The recursive tree branches twice at each level, producing ∼2ⁿ total calls without memoization.
2. Power set generation — Generating all 2ⁿ subsets of a set.
3. Subset sum (brute force) — Check every subset to see if it sums to a target.
4. Tower of Hanoi — Moving n disks requires 2ⁿ - 1 moves.
5. Solving SAT (worst case) — Checking all truth assignments for n boolean variables.

Escape Routes

• Dynamic programming: The naive Fibonacci algorithm is O(2ⁿ), but with memoization it becomes O(n). Similarly, subset sum can be solved in O(n × W) pseudo-polynomial time with DP.
• Branch and bound: Prune branches of the search tree that cannot lead to optimal solutions.
• Approximation algorithms: Accept a near-optimal solution in polynomial time.
• Heuristics: Greedy approaches, simulated annealing, or genetic algorithms for practical solutions.