Online Tool Store
· 4 min read
How to See What Big-O Means at Real Sizes
Heshan Fernando
Co-founder & COO
Everyone knows O(n log n) beats O(n²). Fewer people can say by how much, or at what input size it starts to matter, and both questions have concrete answers.
At n = 100 the difference is a factor of about 15. At n = 10,000 it is about 760. At n = 1,000,000 it is roughly 50,000. The ratio itself grows, which is what “asymptotically better” means and what a chart makes obvious in a way the notation does not.
The numbers at real sizes
| n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 100 | 7 | 100 | 664 | 10,000 |
| 10,000 | 13 | 10,000 | 132,877 | 100,000,000 |
| 1,000,000 | 20 | 1,000,000 | 19,931,569 | 10¹² |
The O(n²) column is the one worth sitting with. At a million items it is a trillion operations — hours to days of computation for something the O(n log n) algorithm finishes in under a second.
That is the practical meaning of a complexity class: not that one is faster, but that one remains possible at scales where the other stops being.
Big-O discards the constants, and the constants decide small cases
Big-O describes growth, not time. It deliberately ignores constant factors and lower-order terms, which is what makes it useful for reasoning about scale and useless for predicting which of two algorithms is faster on twenty items.
Insertion sort is O(n²). Merge sort is O(n log n). For small arrays insertion sort is faster — it has almost no overhead, excellent cache behaviour, and no allocation.
This is not a theoretical curiosity. Real sort implementations exploit it: they use an O(n log n) algorithm for the bulk and switch to insertion sort below a threshold of a few dozen elements, because that is genuinely quicker.
So “which class is better” and “which is faster here” are different questions, and only the first is answered by the notation.
Where each class shows up
O(1) — hash lookup, array index. Independent of size.
O(log n) — binary search, balanced tree operations. Doubling the data adds one step, which is why these scale almost indefinitely.
O(n) — a single pass. Usually the floor for anything that must look at all the data.
O(n log n) — comparison sorting. Proven to be the lower bound for comparison-based sorts, which is why no sort beats it in the general case.
O(n²) — nested loops over the same data. Fine at small n, and the most common accidental complexity in application code.
O(2ⁿ) — brute-force search over subsets. Becomes impossible faster than people expect: around n = 40 it is beyond a laptop, and n = 60 is beyond any hardware that exists.
Amortised and average differ from worst case
A single complexity class frequently hides three different numbers.
Worst case is the guarantee. Quicksort is O(n²) in the worst case, on input that happens to hit its pivot choice badly.
Average case is what usually happens. Quicksort averages O(n log n), which is why it is used despite the worst case.
Amortised describes the average across a sequence of operations. Appending to a dynamic array is O(n) when it resizes and O(1) the rest of the time, averaging O(1) amortised — which is the honest description for anything appending repeatedly.
Which matters depends on the context. A real-time system cares about the worst case; a batch process cares about the average. Quoting one without saying which is where performance surprises come from.
Common mistakes to avoid
- Assuming the lower class is always faster, when constants dominate at small n.
- Optimising complexity for a collection that will never exceed a hundred items.
- Ignoring an O(n²) that is fine today on a dataset that grows.
- Confusing average and worst case — quicksort is O(n log n) typically and O(n²) on adversarial input.
- Treating space complexity as free. An algorithm that trades memory for time can exhaust memory instead.
How to do it with Big-O Complexity Visualizer
The Big-O Complexity Visualizer plots operation counts at real sizes.
- Choose the classes you are comparing.
- Set the input size you actually expect, not an abstract one.
- Read the operation counts, and look at where curves cross.
- Remember the crossing point moves with the constants, which the chart cannot know.
Other developer tools are in the tools directory.
Frequently asked questions
Does a lower complexity class always mean faster?
No. Big-O hides constants, and an O(n²) algorithm with tiny overhead beats an O(n log n) one with large overhead on small inputs. Real sort implementations switch to insertion sort for short runs precisely for this reason.
Why does O(2ⁿ) matter if it is rare?
Because it appears in brute-force approaches to combinatorial problems and becomes unusable very quickly. Around n = 40 it is already beyond a laptop, which is much sooner than most people expect.
Is Big-O about time or memory?
Either. The same notation describes space complexity, and an algorithm that improves one by trading against the other changes both.
Final thought
Look at the numbers at your actual input size. “Asymptotically better” is a statement about behaviour at infinity, and your data is not at infinity.