What big-O says and what it refuses to say
Big-O describes how the work an algorithm does grows as its input grows, and nothing else. Saying an algorithm is O(n²) means that beyond some input size the work is bounded above by a constant multiple of n². It says nothing about the constant, nothing about small inputs, and nothing about seconds.
That abstraction is exactly what makes the notation useful and exactly what makes it useless on its own. Useful, because the constant depends on the language, the compiler, the processor and the memory hierarchy, all of which change, while the growth rate is a property of the algorithm and does not. Useless on its own, because a question like “will this finish before the deadline” is a question about seconds.
Restoring the missing information takes two numbers. The constant factor converts units of f(n) into operations: a sort performing three comparisons and a swap per unit of n log n has a constant near four. The machine speed converts operations into seconds. Multiply and divide, and the asymptotic statement becomes a prediction you can test.
The prediction will be approximate, and the direction of error is usually the same. Real machines do not execute operations at a uniform rate: a sequential scan through an array runs many times faster per element than a pointer chase through a linked list of the same length, because one is served by cache and prefetching and the other is not. Quantify that gap with the cache hit ratio and AMAT calculator. What this calculator gives you is the order of magnitude, and for the decisions big-O is meant to inform, the order of magnitude is what settles the argument.
The classes, and how fast each one really grows
O(1) — the work does not depend on n. A hash lookup, an array index, arithmetic. Doubling n multiplies the work by 1.
O(log n) — the work grows by a constant amount each time n doubles. Binary search over a billion elements takes about 30 steps; over a trillion, about 40. Doubling n adds one operation, so the multiplier is 1 + 1/log₂n, which approaches 1 as n grows. Logarithmic algorithms are effectively free.
O(n) — doubling n doubles the work. Reading a file, summing an array, a single pass over records.
O(n log n) — doubling n slightly more than doubles the work: the multiplier is 2(log₂n + 1)/log₂n, which at n = 106 is about 2.10. This is the bound for comparison-based sorting, and in practice it behaves almost like linear.
O(n²) — doubling n quadruples the work. Nested loops over the same collection, insertion sort, the all-pairs comparison. This is the class where the transition from “fine in testing” to “unusable in production” happens, because a hundredfold increase in data is a ten-thousandfold increase in time.
O(n³) — doubling n multiplies the work by eight. Naive matrix multiplication, triple-nested loops, some dynamic programming formulations.
O(2ⁿ) — each additional element doubles the work. Enumerating every subset. The multiplier when n doubles is 2ⁿ, which is not a number you can reason about casually: at n = 64 doubling the input multiplies the work by 1.8×1019.
O(n!) — enumerating every permutation. Going from n to n+1 multiplies the work by n+1. 20! is 2.4×1018; 21! is 5.1×1019.
The last two are the reason this calculator reports a logarithm. Beyond about 21024 a double-precision number becomes infinity, and the operation count for O(n!) at n = 1,000 is around 102,568. The logarithm keeps the answer readable where the count itself cannot be printed.
Worked example: will an O(n²) join survive production?
A nested-loop join compares every record in one collection against every record in another of the same size. It works fine on a 1,000-record test fixture. Production has 100,000 records. Assume the machine performs 109 simple operations per second and the inner loop costs about 5 operations per pair, so c = 5.
- Test scale. f(1,000) = 1,000² = 106, so operations = 5 × 106 = 5×106, and runtime = 5×106 ÷ 109 = 5 ms. Nobody notices.
- Production scale. f(100,000) = 1010, so operations = 5×1010 and runtime = 5×1010 ÷ 109 = 50 seconds.
- Check the ratio. n grew by 100×, and 100² = 10,000, so the runtime grew from 5 ms to 50 s — exactly 10,000×. The arithmetic is self-consistent.
- What one more doubling costs. At n = 200,000 the work quadruples: 200 seconds.
- What fits in one second. The budget is 109 × 1 ÷ 5 = 2×108 units of f(n), so n = √(2×108) = 14,142. The algorithm supports about fourteen thousand records within a one-second budget.
Now compare the alternative. A hash join is O(n) with a larger constant — say c = 20, because hashing and probing cost more per record than a comparison. At n = 100,000 that is 20 × 100,000 = 2×106 operations, or 2 ms. It is 25,000 times faster than the nested loop despite having a constant factor four times larger.
The crossover is worth computing, because it is where the intuition “the simple algorithm is faster on small inputs” stops being true. Solve 5n² = 20n, giving n = 4. Above four records the hash join wins, and the four-times-worse constant buys the nested loop almost nothing.
How to read the result
Compare the operation count against 108 to 109, which is the range a modern machine completes in about a second for simple operations. Below 108 you are almost certainly fine; above 1010 you are almost certainly not; in between, the constant factor decides and you should measure rather than argue.
Use the doubling factor to plan for growth, because it is the number that tells you whether today's acceptable runtime survives next year's data. An O(n log n) pipeline that runs in ten minutes today runs in about twenty-one minutes at twice the data. An O(n²) pipeline runs in forty minutes. An O(n³) one runs in eighty. Those three futures need very different responses, and the difference is invisible in a single measurement of today.
Use the maximum-n figure when the budget is fixed. Competitive programming makes this explicit — a one-second limit and n ≤ 105 is a strong hint that the intended solution is O(n log n), because 105 × 17 is well inside a second while 1010 is not. The same reasoning applies to a request that must return within 200 ms.
Treat the constant factor as the thing you measure, not the thing you guess. Run the code at a known n, count or time the work, and divide by f(n). Do it twice at different sizes: if the derived constant is stable, your complexity assumption is right; if it grows with n, the real complexity is worse than you thought and the discrepancy tells you by how much. This is the single most useful thing you can do with this calculator, and it turns a rough estimate into a calibrated one.
Finally, remember that parallelism changes the constant, not the class. Sixteen cores can give you a sixteen-fold speedup at best and rather less in practice, which moves an O(n²) workload from fifty seconds to perhaps four — one doubling of n and you are back where you started. The Amdahl's law speedup calculator puts a ceiling on what parallelism can buy, and the ceiling is usually lower than people expect.
Operations by complexity class and input size
| f(n) | n = 10 | n = 100 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| log₂ n | 3.32 | 6.64 | 9.97 | 19.93 |
| n | 10 | 100 | 1,000 | 1×106 |
| n log₂ n | 33.2 | 664 | 9,966 | 1.99×107 |
| n² | 100 | 10,000 | 1×106 | 1×1012 |
| n³ | 1,000 | 1×106 | 1×109 | 1×1018 |
| 2ⁿ | 1,024 | 1.27×1030 | 1.07×10301 | 10301,030 |
| n! | 3,628,800 | 9.33×10157 | 4.02×102,567 | 105,565,709 |
At 10⁹ operations per second, the n = 1,000,000 column reads: n log n takes 20 ms, n² takes about 17 minutes, and n³ takes about 31.7 years. Those three lines are the whole argument for caring about complexity.
Largest n that fits one second at 10⁹ operations per second
| Complexity | Largest n in 1 second | Typical algorithm |
|---|---|---|
| O(1) | any n | Hash lookup, array index |
| O(log n) | astronomically large | Binary search, balanced tree lookup |
| O(n) | 1×109 | Linear scan, counting sort |
| O(n log n) | 3.96×107 | Merge sort, heap sort, most practical sorts |
| O(n²) | 31,622 | Insertion sort, all-pairs comparison |
| O(n³) | 1,000 | Naive matrix multiply, Floyd–Warshall |
| O(2ⁿ) | 29 | Subset enumeration, naive SAT |
| O(n!) | 12 | Permutation search, brute-force TSP |
Read the last two rows carefully: doubling machine speed adds one to the O(2ⁿ) limit and does not reliably add anything to the O(n!) limit. For exponential and factorial problems, hardware is not a lever.
Where this estimate goes wrong
- Memory access is not one operation. A cache hit costs a few cycles and a main-memory miss costs a few hundred. Two O(n) algorithms can differ by a factor of ten purely on access pattern.
- Big-O hides the constant, and the constant sometimes wins. Insertion sort beats merge sort on small arrays, which is why real sort implementations switch to it below a threshold of a few dozen elements.
- Average and worst case can differ. Quicksort is O(n log n) expected and O(n²) worst case; a hash table is O(1) expected and O(n) when every key collides. Decide which case you are budgeting for.
- Amortised is not per-operation. A dynamic array append is O(1) amortised, but the individual append that triggers a resize is O(n). That matters when the metric is tail latency rather than throughput.
- n is not always the obvious quantity. Graph algorithms are usually expressed in vertices and edges together, and string algorithms in pattern and text length. A single n loses that structure.
- Input and output cost real time. Reading ten million lines from disk can dominate a linear algorithm's entire compute budget. Size the transfer separately with the data transfer time calculator.
- Compilers and interpreters differ by orders of magnitude. The same algorithm can be fifty times slower in an interpreted language. That is a constant-factor difference, so it moves the runtime and not the class.
- The asymptotic bound may not apply at your n. Big-O describes behaviour for sufficiently large n, and some algorithms with excellent asymptotics have constants so large they never win at realistic sizes.
Key terms
- O, Ω and Θ
- O is an upper bound, Ω a lower bound, and Θ a tight bound that is both. Saying an algorithm is O(n²) does not claim it is ever that slow; Θ(n²) does.
- Constant factor
- The number of actual operations per unit of f(n). Big-O discards it by definition, and it is what determines whether an asymptotically worse algorithm is faster at your input size.
- Amortised complexity
- The average cost per operation over a sequence, where occasional expensive operations are spread across many cheap ones. A dynamic array append is O(1) amortised despite occasional O(n) resizes.
- Crossover point
- The input size at which two algorithms take the same time. Below it the one with the smaller constant wins; above it the one with the better growth rate does.
- Pseudo-polynomial
- An algorithm polynomial in the numeric value of an input rather than in the number of bits used to write it. The knapsack dynamic program is the standard example.
When complexity is not the right question
Complexity analysis answers “how does this scale”. Three other questions frequently matter more, and none of them is answered by a growth rate.
The first is where the time actually goes. Profiling routinely shows that the asymptotically dominant loop is not the bottleneck at real input sizes, because a constant-time operation inside it makes a network call. Measure before you optimise; an O(n²) loop over 200 items is 40,000 operations and takes microseconds.
The second is what the memory hierarchy is doing. Two algorithms with identical complexity can differ by an order of magnitude on access pattern alone, which is why array-of-structs versus struct-of-arrays and cache-oblivious layouts are worth as much as an algorithmic improvement in numerical code.
The third is how much concurrency helps. Parallelism divides the constant by the number of workers, up to the limit imposed by whatever fraction of the program is inherently serial — the ceiling that Amdahl's law makes precise. It never changes the complexity class, so it buys you a fixed factor once and then stops. Queueing behaviour under load is a separate question again, governed by the relationship between arrival rate, service time and concurrency that Little's law captures.
Where complexity is the right question, it is decisive in a way nothing else is. No constant factor, no hardware upgrade and no amount of parallelism rescues an exponential algorithm at n = 100. That is the case in which you stop tuning and change the algorithm.