Big-O notation describes the shape of an algorithm's cost as its input grows —
deliberately throwing away constant factors and lower-order terms to make that shape comparable
across completely different algorithms. That's exactly why it's useful, and exactly why it's easy
to misjudge in practice: "O(n²) is worse than O(n log n)" is true, but
says nothing about how much worse, or at what size of n it starts to matter.
This page puts real numbers behind the shapes. Drag n up by orders of magnitude and
watch what each class actually costs, both in raw operation counts and — assuming a machine doing
a billion operations a second, a reasonable modern ballpark — in wall-clock time.
Move the slider to change n from ten to a billion. Every row recomputes live: the
bar is each class's operation count on a log scale (linear would make everything except
O(n³) vanish), and the right-hand figure is that same operation count converted into
time at one billion operations per second.
Every class above stays within reach of each other even at n = 1,000,000,000 —
polynomial growth is dramatic, but not catastrophic. Exponential and factorial growth are a
different kind of thing entirely: they don't slow down, they hit a wall, and the wall shows up at
surprisingly small n. Try dragging this one from 1 up toward 100 and watch how fast
both figures below stop meaning anything on a human timescale.
The same numbers as the slider above, pinned at three landmark sizes, for a quick lookup without touching anything:
| class | n = 10 | n = 1,000 | n = 1,000,000 |
|---|
Each row above is a real cost class, not just a textbook shape — here's one entry from this site landing on each one, checked against that page's own Complexity section rather than assumed:
O(1) — Hash Table: amortized
average O(1) get/put/delete — worst case still degrades to O(n) if
every key collides into the same bucket.O(log n) — Binary Search: each
comparison halves the remaining range, but only works because the array is already sorted.O(√n) — Sqrt
Decomposition: block size b ≈ √n balances two terms — block count and
in-block scan — that would otherwise trade off against each other. One of the few structures on
this site whose whole design point is landing on exactly this class.O(n) — Linear Search: no
shortcuts, provably the best any comparison-based search can do without more structure than an
unordered array.O(n log n) — Merge Sort:
O(n log n) in every case, not just on average — that guarantee (plus
stability) is why it backs the standard sort in Python, Java, and others.O(n²) — Insertion Sort: worst
and average case; best case drops to O(n) on already-sorted input, one algorithm
straddling two rows of this page depending on the input.O(n³) — Floyd-Warshall: three
nested loops over every vertex, all-pairs shortest paths in one pass, independent of how many
edges actually exist.O(2ⁿ) — Subset Sum (backtracking):
worst case — pruning cuts the constant factor a lot in practice, but a target exactly one more
than the total sum forces the search to rule out every subset anyway.For how a whole category's worth of algorithms stack up against each other rather than one class at a time, see the site's other guides — Choosing a Comparison Sort and Choosing a Search Algorithm both include a live race of their own.