Polynomial, Exponential and Factorial Growth
A delivery company has 10 stops. Checking every pair of stops for the shortest link takes a moment. Checking every order in which to visit them means 3,628,800 routes. At 20 stops, the pairs are still easy, but the orders number in the quintillions. Knowing which kind of counting your algorithm does is the difference between "instant" and "never".
The rule
Nested loops give powers; yes-or-no choices give 2ⁿ; orderings give n!.
Three families grow faster than linear:
- Polynomial, like n² or n³. Comes from loops inside loops over the input. Comparing every item with every other item is about n².
- Exponential, 2ⁿ. Comes from making an independent yes-or-no choice for each item: every subset of n items. Each extra item doubles the work.
- Factorial, n! = n × (n − 1) × … × 1. Comes from trying every ordering of n items. Each extra item multiplies the work by the new n.
The numbers pull apart fast:
| n | n² | 2ⁿ | n! |
|---|---|---|---|
| 5 | 25 | 32 | 120 |
| 10 | 100 | 1,024 | 3,628,800 |
| 20 | 400 | 1,048,576 | about 2.4 × 10¹⁸ |
Put the whole ladder together, slowest-growing first: 1, log n, n, n log n, n², n³, 2ⁿ, n!.
The shortcut
Ask what the algorithm is enumerating. Pairs or triples of items: polynomial. Subsets, or each item in or out: exponential. Arrangements or orders: factorial.
Find duplicate names by comparing every pair
Every item against every other item: pairs, so about n².
The trap is judging from small inputs. At n = 5, 2ⁿ (32) barely beats n² (25). The difference only shows as n grows, which is exactly when it hurts.
Drills
Answer fast — trust the rule.
Two nested loops each run over all n items. What is the growth rate?
An algorithm checks every subset of 20 items. About how many subsets is that?
An exponential algorithm handles 30 items in 1 second. Roughly how long for 31 items?
Which order runs from slowest-growing to fastest-growing?
Remember
- Nested loops give powers of n; in-or-out choices give 2ⁿ; orderings give n!.
- The ladder: 1, log n, n, n log n, n², n³, 2ⁿ, n!.
- The trap: small inputs hide the gap; exponential and factorial explode as n grows.