How cost grows
A million items. O(n log n) finishes in a blink. How long does O(n²) take at the same speed?
Every rung of the ladder is a shape of code, from a single loop to a loop inside a loop to every ordering of the input. One dial moves the input size, and the operation counts and times beside each rung move with it. Small inputs make the rungs look alike, and a million items pulls them apart.
Board: Complexity and Big-O →On a narrow screen, the ladder scrolls sideways. The slider and the key numbers stack above it.
try this Drag Input size, n up to a million and watch the Off the chart panel count rungs that now read never.
Every time on this page assumes 1,000,000,000 operations a second. This is an assumption, not a measurement. The operation counts are exact. A different rate would change the times, but the gap between rows stays the same shape.
A million items. O(n log n) finishes in a blink. How long does O(n²) take at the same speed?
O(n log n)
a sort, or a search that halves per item
19,931,569
operations
O(n²)
a loop inside a loop, both over the input
1,000,000,000,000
operations
Off the chart
rungs whose count at this n is too large to print
2
of 7 rungs are already "never"
The ladder
| Rung | How to spot it | Operations at n = 1,000,000 | Time at the assumed rate |
|---|---|---|---|
| O(1) constant | no loop over the input: an array index, a hash lookup, a fixed number of steps | 1 | instant |
| O(log n) logarithmic | the search range halves (or shrinks by another constant fraction) every step | 20 | instant |
| O(n) linear | one loop over the input, doing a constant amount of work per item | 1,000,000 | 1 ms |
| O(n log n) linearithmic | a loop that halves its range, run once per item, or a sort | 19,931,569 | 20 ms |
| O(n²) quadratic | a loop inside a loop, each over the input, comparing every item with every other | 1,000,000,000,000 | 16 min 40 s |
| O(2ⁿ) exponential | a function that calls itself twice per item, visiting every subset of the input | never | never |
| O(n!) factorial | every ordering of the input, with one level of nesting per item | never | never |
Read it off the code
One loop over n, with a constant amount of work per item, is linear. A loop inside a loop, each over the input, multiplies the work: quadratic. Halving the search range every step gives logarithmic. A sort that halves its range once per item is n log n. You can read the class from the nesting in the code.
Drop the constants
As n grows, only the biggest term matters. 2n + 3 is just n, because the plus three stops mattering once n is more than a handful. n² + 100n is just n², because the 100n term is a rounding error once n reaches the thousands. Big-O keeps only the term that decides how cost grows.
Pick the complexity first
Machines get faster every year, so a benchmark today says little about next year's hardware. Operations as a function of n do not change when the CPU does. Fix a quadratic loop before you shave milliseconds off it.
Limits of this model
1,000,000,000 operations a second is an assumption, not a measurement. No real machine runs at a constant rate. Cache misses, branch prediction, garbage collection and parallelism move the true number by orders of magnitude. A different rate changes every time on this page. The gap between rungs keeps its shape, and that shape is what this lab shows.
Dropping the constants can be wrong at small n. Big-O keeps only the leading term. A linear algorithm with a large constant can lose to a quadratic one with a tiny constant until n grows large enough. This lab shows only the leading term and does not model that crossover. At small n, a real choice between two algorithms sometimes has to.
"Never" is a cap, not infinity. O(2ⁿ) and O(n!) are computed only while the result is still a readable duration. Past that, the lab shows "never" instead of a number with hundreds of digits. The true counts are finite, but they grow too large to print long before n reaches a million.
Sources
see also The Bitter Lesson, MapReduce: Simplified Data Processing on Large Clusters and Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities in Papers.