Exponential Time
Runtime that doubles with each added element.
Formula
Variables
Example
Naive subset enumeration
How it works
O(2^n) describes algorithms whose work doubles whenever the input grows by just one element, because they explore two choices for each item: include it or exclude it. This creates a complete binary decision tree with about 2^n leaves, so the total number of states or recursive calls grows exponentially rather than linearly or quadratically. The notation hides constant factors and lower-order terms, but the key idea is that even small increases in n make the running time explode.
When to use it
Use this model when an algorithm systematically branches on each of n independent yes/no decisions, such as backtracking over combinations, recursive search over subsets, or solving exact NP-hard problems by brute force. It is especially relevant when you need to estimate why a method becomes infeasible beyond modest input sizes.
Worked example, step by step
Suppose a recursive search over n = 5 items branches into two choices at each item. Step 1: Count the number of leaves in the decision tree: 2^5 = 32. Step 2: That means the algorithm may examine up to 32 distinct combinations. Step 3: If each combination takes 3 microseconds to evaluate, total time is 32 × 3 = 96 microseconds. Step 4: If n increases to 6, the work becomes 2^6 = 64 combinations, which is exactly double the previous amount. Final answer: the runtime scales as O(2^n), so going from 5 to 6 items doubles the work from 32 to 64 combinations.
Common mistakes to avoid
- Confusing 2^n with n^2; exponential growth is much faster than polynomial growth
- Treating O(2^n) as exact runtime instead of an upper-growth bound
- Forgetting that branch pruning or memoization can reduce the practical runtime below 2^n
Did You Know?
Exponential-time problems explode so fast that adding one input can double the entire runtime.
Share this formula
More in Computer Science
View allShannon Entropy
AdvancedAverage information content of a random source (bits).
Master Theorem (form)
AdvancedAnalyzes running time of divide-and-conquer algorithms.
Hamming Distance
AdvancedNumber of positions at which two strings differ.
Bits to Represent n
BasicMinimum number of bits to represent n distinct values.
Binary to Decimal
BasicConverts a binary number to decimal.
Nodes in a Full Binary Tree
IntermediateTotal nodes in a perfect binary tree of height h.