Compare growth classes, data structure operations and sorting bounds, with notes on the constant factors Big O leaves out.
At 10,000 items
Operation counts are exact arithmetic on the growth functions. The durations assume one billion simple operations per second and no memory effects at all, so treat them as orders of magnitude rather than measurements — a cache miss costs a hundred times what a register operation does, and Big O cannot see the difference.
| Class | Notation | Operations | Rough duration | Verdict |
|---|---|---|---|---|
| Constant | O(1) | 1 | under a microsecond | excellent |
| Logarithmic | O(log n) | 14 | under a microsecond | excellent |
| Square root | O(√n) | 100 | under a microsecond | good |
| Linear | O(n) | 10 thousand | 10 microseconds | good |
| Linearithmic | O(n log n) | 133 thousand | 133 microseconds | good |
| Quadratic | O(n²) | 100.0 million | 100 milliseconds | acceptable |
| Cubic | O(n³) | 1.0 trillion | 17 minutes | poor |
| Exponential | O(2ⁿ) | more than atoms in the universe | longer than the universe has existed | unusable |
| Factorial | O(n!) | more than atoms in the universe | longer than the universe has existed | unusable |
| n = | 1 | 10 | 100 | 1,000 | 10,000 | 100,000 | 1,000,000 |
|---|---|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| O(log n) | 1 | 4 | 7 | 10 | 14 | 17 | 20 |
| O(√n) | 1 | 4 | 10 | 32 | 100 | 317 | 1.0 thousand |
| O(n) | 1 | 10 | 100 | 1.0 thousand | 10 thousand | 100 thousand | 1.0 million |
| O(n log n) | 1 | 34 | 665 | 10.0 thousand | 133 thousand | 1.7 million | 19.9 million |
| O(n²) | 1 | 100 | 10 thousand | 1.0 million | 100.0 million | 10.0 billion | 1.0 trillion |
| O(n³) | 1 | 1.0 thousand | 1.0 million | 1.0 billion | 1.0 trillion | 1000.0 trillion | more than atoms in the universe |
| O(2ⁿ) | 2 | 1.0 thousand | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe |
| O(n!) | 1 | 3.6 million | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe | more than atoms in the universe |
O(1)ConstantexcellentThe work does not depend on the input size at all. A million items cost the same as one.
Reading an array element by index, or a hash table lookup once the hash is computed.
O(log n)LogarithmicexcellentDoubling the input adds one step. A billion items take about thirty.
Binary search, and lookups in a balanced tree.
O(√n)Square rootgoodWork grows, but far slower than the input. A million items take a thousand steps.
Jump search, and trial division when testing whether a number is prime.
O(n)LineargoodThe work is proportional to the input. Twice the data, twice the time.
Scanning a list, or counting how many items match.
O(n log n)LinearithmicgoodA little worse than linear, and the practical floor for comparison sorting — no comparison sort can beat it.
Merge sort, heapsort, and every standard library sort.
O(n²)QuadraticacceptableTen times the data is a hundred times the work. Fine for hundreds of items, painful for thousands.
Bubble sort, and any pair of nested loops over the same collection.
O(n³)CubicpoorTen times the data is a thousand times the work. Usable only on small inputs.
Naive matrix multiplication, and the Floyd–Warshall shortest-path algorithm.
O(2ⁿ)ExponentialunusableEach extra item doubles the work. Adding one element to a tractable problem can make it intractable.
Enumerating every subset, and naive recursive Fibonacci.
O(n!)FactorialunusableEvery ordering of the input. Twenty items is already more orderings than there are grains of sand.
Trying every permutation, as in the brute-force travelling salesman.
Big O drops constant factors, and on real hardware the constants are often what decides the race. A linear scan of an array reads whole cache lines at a time; a walk down a linked list is a chain of cache misses. The array wins up to surprisingly large sizes despite identical bounds.
It also says nothing about which case you are in. A hash table is O(1) on average and O(n) when the keys collide — and if an attacker chooses the keys, they decide which.
And it is about growth, not about small inputs. Real library sorts switch to insertion sort below roughly sixteen elements, because O(n²) with a tiny constant beats O(n log n) with a large one at that size.
Use it to decide whether an approach scales. Measure to decide which implementation is faster.
Complexity Reference runs entirely on your device — every figure is computed in the page and nothing is uploaded.
You’re on the Free plan. Compare plans
Three tables, and the practical notes that stop them being misleading. Big O is the right tool for deciding whether an approach scales and the wrong tool for predicting which of two implementations is faster, so both halves are here.
A table of bounds with nothing about constant factors teaches people to reach for a linked list — O(1) insertion, textbook-superior — which loses to an array on nearly every real workload, because the array's elements sit together in memory and a walk down a list is a chain of cache misses. Every structure row carries a note saying what the bound leaves out.
The growth figures are arithmetic on the growth functions rather than copied from a table, so they cannot drift out of step with the classes they illustrate. They are rounded up and floored at one operation, because log2(1) is exactly zero and a table claiming a binary search on one element takes no work is correct and useless.
The duration column states its assumption next to the numbers: one billion simple operations a second, and no memory effects at all. That is the right order of magnitude for a modern core and wrong by a factor of several for any specific program. It is there because 10^12 operations means nothing to most people and "about twenty minutes" means something.
Where a worst case differs from an average, the note says when the worst case happens. A hash table shown as O(1) average and O(n) worst with no explanation of colliding keys is where the dangerous half of a reader's understanding comes from — and if an attacker chooses the keys, they choose which case you are in.
Because the O(1) assumes you already hold a pointer to the position, and finding it is O(n). Beyond that, every node is a separate allocation, so traversal is a chain of cache misses while an array scan reads whole cache lines. Big O drops exactly the constant that decides this.
When the keys collide, which makes every operation a scan of one bucket. If an attacker can choose the keys, they can force it — which is a denial-of-service vector and the reason languages randomise their hash seed per process.
No, and the table says so. They assume one billion simple operations per second and no memory effects, so treat them as orders of magnitude. A cache miss costs a hundred times what a register operation does, and Big O cannot see the difference.
Because it is genuinely fast on small and nearly-sorted inputs, and the constant factor is tiny. Standard library sorts switch to it below roughly sixteen elements. That is the clearest example of why a bound is not a benchmark.