# O(2ⁿ) - Exponential Time

> Doubles with every extra element — n=50 already takes longer than the age of the universe.

- **Category**: Big O
- **Subcategory**: Danger Zone
- **Canonical URL**: https://designpattern.fyi/patterns/exponential-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
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.



## Implementation Example

```javascript
// ❌ 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
}

```



## Trade-offs


### 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




### Considerations & Drawbacks

- 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







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)