Foundations
Growth rates & Big-O curves
Plot O(1)…O(n!) on one chart; watch how each bound scales as n grows.
Question: is O(n²) OK for n ≤ 10⁴?
It depends on the cap. 10⁴ × 10⁴ = 10⁸ operations blow a 1-second judge budget on its own. If n ≤ 10⁵ then O(n²) = 10¹⁰ and you time out. This page exists to make "is this bound fast enough?" a 5-second visual and numerical call.
By the numbers
| n | log₂ n | n | n log n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10³ | 10 | 10³ | 10⁴ | 10⁶ | ~10³⁰⁰ |
| 10⁶ | 20 | 10⁶ | 2·10⁷ | 10¹² | blows up |
| 10⁹ | 30 | 10⁹ | 3·10¹⁰ | 10¹⁸ | blows up |
One line: log n stays tiny even for huge n, n log n is survivable at 10⁶, n² dies past 10⁵, 2ⁿ is physically impossible past n ≈ 30.
Where each one comes from
Every loop shape maps to a growth class:
- One loop over 1..n: touch each element once →
O(n). - Two nested loops, both n: total iterations
n · n = n²→O(n²). Even if the inner loop averages n/2, you drop the constant and it's stillO(n²). - Divide-and-conquer halves each step: n → n/2 → n/4 → … 1. That's
log₂ nhalvings. Each level touches the array once (n work) →n · log n→ O(n log n). - Subset enumeration: each element include/exclude, two choices →
2 · 2 · … · 2 = 2ⁿ→ O(2ⁿ).
Trap: "merge sort has nested loops, so it's O(n²)"
Wrong. The inner loop in merge sort is for a single level, and each level touches the entire array once (n work). What looks nested is actually n work at each of log n levels: n · log n, not n · n. Same fallacy: "there are two loops, so O(n²)". Sequential loops add (n + n = 2n → O(n)), they don't multiply.
Where to go next
- Complexity & Big-O: the practical loop-counting page.
- Logarithms: why log n is "almost constant".
- binary-search pattern: where O(log n) is born.
Exercise
Pause the chart and set n = 20. Predict the O(n²) andO(n log n) values, then hover them. Now bump to n = 40: how many times did the gap grow?