Back to Catalog
Big O
Danger Zone
O(2ⁿ) - Exponential Time
Doubles with every extra element — n=50 already takes longer than the age of the universe.
Intent & Description
Real-world Use Case
Naive recursive Fibonacci — fib(50) calls fib(49)+fib(48), each of which calls fib(48)+fib(47)… resulting in 2⁵⁰ calls. With memoization, it reduces to 50 unique subproblems — O(n). Generating the power set of n items is inherently O(2ⁿ) — there are 2ⁿ subsets, so you cannot do better.
Source
📌 TL;DR
O(2ⁿ) = recursion tree that doubles every level. fib(50) naive would take years. Apply memoization or DP to turn it into O(n). If you must enumerate all subsets, accept it only for n < 20.
Advantages
- Naturally expressive — recursive solutions map directly to problem structure
- Correct and simple to implement for small n
- Sometimes the only correct approach (power sets, certain combinatorial enumerations)
- Acts as a forcing function to learn DP and memoization
Disadvantages
- Completely unusable past n=30-40 without optimization
- The most dangerous complexity to accidentally write — recursive branching feels innocent
- Looks fast in tests (small n) and explodes in production (realistic n)
- Tree of calls is exponentially deep — stack overflow risk on top of time blow-up
Implementation Example
// ❌ O(2ⁿ) — Naive recursive Fibonacci (calculates same values millions of times)
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
// Recursion tree has 2^n nodes — fib(50) makes ~2^50 calls
}
// ✅ O(n) time, O(n) space — Memoization (top-down DP)
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n); // Cache hit — O(1)
memo.set(n, fibMemo(n-1, memo) + fibMemo(n-2, memo));
return memo.get(n);
// Each unique n computed exactly once — O(n) total calls
}
// ✅ O(n) time, O(1) space — Bottom-up DP (best for Fibonacci)
function fibDP(n) {
if (n <= 1) return n;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
return b;
}
// O(2ⁿ) — Power set generation (inherently exponential — 2^n subsets exist)
function powerSet(arr) {
if (arr.length === 0) return [[]];
const [head, ...rest] = arr;
const subsetsWithoutHead = powerSet(rest);
return [...subsetsWithoutHead, ...subsetsWithoutHead.map(s => [head, ...s])];
// Always O(2^n) — cannot be avoided as there are 2^n subsets
}