Is an O(n) algorithm always faster than an O(n²) one? Watch six costs race as n doubles, tangled at first, then far apart.
How fast different costs grow
Six growth classes as n doubles from 2 to 1024
n = 2: the axis ends at 2 n log₂ n = 4. Every curve fits.
- 1
- 1
- log₂ n
- 1
- n
- 2
- n log₂ n
- 2
- n²
- 4
- 2ⁿ
- 4
Describe this picture
A plot with no code. Six curves, one per growth class, are drawn from n = 1 to the current n: 1 (dashed) and log₂ n in the third colour, n and n log₂ n (dashed) in the first, n² and 2ⁿ (dashed) in the second, named in a legend above the plot. The clip doubles n from 2 to 1024, one beat each, about 10 seconds. Both axes rescale at every beat: across to n, and up to 2 n log₂ n, so the n log₂ n curve always ends at half height. At n = 2 and 4 every curve fits, n² and 2ⁿ ending exactly at the top. From n = 8 on, n² and 2ⁿ rise out of the frame, while 1 and log₂ n flatten onto the floor and n sinks below n log₂ n. Under the plot are one sentence on the current n and six readouts, one per class, with its value at that n; at 1024 they read 1, 10, 1,024, 10,240, 1,048,576 and 2¹⁰²⁴ ≈ 1.8 × 10³⁰⁸. After the clip, the slider “n” (2 to 1024 in doublings) stops it at one n. The transport plays and pauses, steps one beat back or forward, and scrubs; n and a paused step are kept in the page address as growth.n and growth.step.
Growth, not time
Counting steps gave each algorithm a count: n steps for one loop, n(n − 1)/2 for all pairs. Big-O keeps only the part of a count that decides how it grows for large n. It throws away constant factors, which depend on the machine, and smaller terms, which stop mattering once n is large.
The clip shows why only large n counts. At n = 4, n² and 2ⁿ are both 16, and n log₂ n is 8: the order of the curves at small n is not their order at large n. A cost of 100n is larger than n² for every n below 100. Big-O is about what happens after the curves stop crossing.
The code and its cost
The definition
f(n) = O(g(n)) when there are a constant c > 0 and a starting point n₀ such that
From n₀ on, the curve of f stays under the curve of c·g. The definition says nothing about n below n₀, and it is an upper bound: 100n is O(n²), but n² is not O(100n). Big-O gives a growth rate, not a run time: two O(n) programs can differ in speed by any constant factor.
Six classes
| Class | Name | Typical code |
|---|---|---|
| O(1) | constant | read one array cell |
| O(log n) | logarithmic | a loop that halves what is left (binary search) |
| O(n) | linear | one loop over the input |
| O(n log n) | n log n | a halving loop inside a loop over n; good sorts |
| O(n²) | quadratic | a loop over all pairs |
| O(2ⁿ) | exponential | try every subset |
log₂ n is small: it is about how many times n can be halved before it reaches 1, about 10 for a thousand (9.97) and about 20 for a million (19.93). It is nothing like n.
Reading a class off code
- Drop constants and smaller terms. 3n² + 5n + 2 is O(n²); 2n is O(n).
- Steps in sequence add, and the larger term wins: an O(n) loop followed by an O(n²) loop is O(n²).
- Nested loops multiply: a loop over n inside a loop over n is O(n²).
- A loop that halves or doubles its variable runs about log₂ n times.
Space
Space complexity counts the extra memory a function needs beyond its input. A function that sorts an array where it lies, with a few variables, uses O(1) extra: it works in place. A function that makes a copy of its n inputs uses O(n). The stack counts too: a recursion that goes n calls deep keeps n frames at once, so it uses O(n) memory even if each frame is small. Chapter 4 draws those frames.
Worked example
Checking the definition. f(n) = 3n² + 5n + 2 is O(n²). With c = 10 and n₀ = 1 it works, since 5n ≤ 5n² and 2 ≤ 2n² for n ≥ 1, so f(n) ≤ 3n² + 5n² + 2n² = 10n². A tighter c needs a later start. With c = 4: at n = 5, f(5) = 102 > 100 = 4 · 5²; at n = 6, f(6) = 140 ≤ 144. From there on 4n² − f(n) = n² − 5n − 2 only grows, so n₀ = 6 is the smallest start for c = 4.
Reading loops.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
... /* n · n: O(n²) */
for (i = 1; i < n; i *= 2)
... /* about log₂ n times: O(log n) */The first is n² steps. The second runs ⌈log₂ n⌉ times: for n = 1000, i takes the values 1, 2, 4, …, 512, which is 10 times. Put that halving loop inside a loop over n and the total is O(n log n). A loop to n followed by another loop to n is 2n steps, which is O(n).
What a million costs. Take n = 10⁶ and a machine doing 10⁹ steps a second. log₂ n ≈ 20 steps, no time at all. n log₂ n ≈ 2 × 10⁷ steps: 0.02 seconds. n² = 10¹² steps: about 1,000 seconds, some 17 minutes. 2ⁿ is out of reach long before a million: at n = 60, 2⁶⁰ ≈ 1.15 × 10¹⁸ steps take about 36 years.
Three checks. Is 100n = O(n²)? (Yes: O( ) is an upper bound.) Is n² = O(100n)? (No.) What is the class of for (i = n; i > 0; i /= 2)? (O(log n).) How much extra space does the sum in Arrays and pointers need? (O(1): a total and an index.)
Where it’s used
Library documentation. Sorting, searching and hash tables are described by their costs: a sort in O(n log n), a lookup in O(1) on average, a binary search in O(log n).
The FFT. The direct DFT of n samples takes n² steps and the fast Fourier transform n log₂ n; at n = 1024 that is about 10⁶ against 10⁴. The FFT is why spectra are cheap to compute.
Design reviews. “This is quadratic in the number of users” is how a slow design is caught before it ships.
Reference card
| Code or idea | Meaning |
|---|---|
| f(n) = O(g(n)) | for some c > 0 and n₀, f(n) ≤ c·g(n) for every n ≥ n₀ |
| drop | constant factors and smaller terms |
| sequence | add: the larger class wins |
| nesting | multiply |
| halving loop | about log₂ n times |
| in place | O(1) extra memory |
| n = 10⁶ | log₂ n ≈ 20, n log₂ n ≈ 2 × 10⁷, n² = 10¹² |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.