What O-notation does not say

$f(n) = O(g(n))$ means: there exist constants $c > 0$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

That is the whole definition. Everything people believe about big-O that is not in that sentence is something they added.

The sentence contains two escape hatches, and almost every misuse of the notation comes from forgetting one of them. The first is $c$: an arbitrary constant, unbounded, chosen after the fact to make the inequality work. The second is $n_0$: an arbitrary threshold, also unbounded, below which the statement says nothing whatsoever.

So “merge sort is $O(n \log n)$” says that beyond some size, merge sort’s cost stays under some multiple of $n \log n$. It does not say the multiple. It does not say the size. And below that size it is not a claim at all.

The definition, walked through slowly #

It repays a careful reading, because every misuse is a misreading.

There exist constants $c > 0$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

“There exist.” Not “for the constant anyone would expect”, not “for a reasonable constant”. Any constant at all. An algorithm that performs $10^{40} \cdot n$ operations, it is $O(n)$, and it is linear, and it is also useless. The notation has no opinion about the size of $c$ and cannot be made to have one.

“For all $n \ge n_0$.” The behaviour below $n_0$ is unconstrained. An algorithm that performs $2^n$ operations for $n < 100$ and $n$ operations thereafter is $O(n)$. This sounds artificial until one notices that it describes several real algorithms with expensive precomputation, and exactly describes any algorithm with a large fixed setup cost.

$f(n) \le c \cdot g(n)$. One-sided. This is the part that makes $O$ so much weaker than people use it as. Since $n \log n \le n^2$ for $n \ge 2$, merge sort is $O(n^2)$, and saying so is not a mistake — it is a true statement that happens to waste most of what is known.

The consequence of all three together: $O$ is a very weak claim, and it is routinely used to make a strong one. When somebody rejects an algorithm because it is $O(n^2)$, they are usually reasoning as though the bound were tight, the constant were ordinary and $n_0$ were small. Often all three are true. The notation does not say so.

O, Θ and Ω, and why the distinction is not pedantry #

Three symbols get used where one is meant, and the sloppiness costs something real.

$f = O(g)$ — $f$ grows no faster than $g$. An upper bound. Merge sort is $O(n \log n)$; it is also $O(n^2)$, and $O(n^{100})$, and $O(2^n)$. All of those are true statements. Only the first is useful, and the notation does not distinguish useful upper bounds from vacuous ones.

$f = \Omega(g)$ — $f$ grows no slower than $g$. A lower bound. Merge sort is $\Omega(n \log n)$ and also $\Omega(n)$ and $\Omega(1)$.

$f = \Theta(g)$ — both. $f$ grows at the same rate as $g$, up to constants. This is almost always the statement people intend when they write $O$, and it is strictly stronger.

The practical consequence: when somebody says an algorithm is $O(n^2)$, they may mean that it has been proved at worst quadratic, or they may mean that it is quadratic. The first leaves room for it to be much better than that. The second does not. The notation does not distinguish them, and the difference matters when the claim is being used to reject an algorithm.

This site uses $\Theta$ where it means $\Theta$, and its fitting machinery tests for $\Theta$ specifically — the ratio $\text{count}/f(n)$ must be bounded above and below, which is exactly the two-sided condition. An algorithm that satisfied only the upper bound would show a ratio drifting downwards, and would be refused.

What the notation throws away #

Four things, in increasing order of how often they matter.

The constant factor. $\Theta(n \log n)$ says the count is some multiple of $n \log n$. Merge sort’s multiple is 0.838. Heapsort’s is 1.613. Both are correct and the second is 1.9 times the first, forever, at every size. That factor is the entire difference between the two algorithms by this measure and the notation is designed to be blind to it.

The lower-order terms. Insertion sort’s comparison count on random input is about $n^2/4$, and it is exactly $\frac{n^2}{4} +$ terms in $n$ and constants. At n = 20 the lower-order terms are a large fraction of the total. At n = 20,000 they are irrelevant. Asymptotic notation is about the second regime, and a lot of real code lives in the first.

The threshold $n_0$. The claim begins somewhere and the notation never says where. An algorithm that is $O(n \log n)$ with $n_0 = 10^{12}$ is, for every practical purpose, an algorithm about which nothing has been said.

The input. This one is not usually counted as part of the notation and it does more damage than the others together. “Insertion sort is $O(n^2)$” is a statement about the worst case. On sorted input insertion sort performs $n - 1$ comparisons, which is $\Theta(n)$, and the same code is being described. Unless the input distribution is named, the class is ambiguous by a factor that can be arbitrarily large.

An algorithm in a worse class winning at every practical size #

The clean illustration is not hypothetical and it is not exotic.

Consider insertion sort against merge sort. Insertion sort is $\Theta(n^2)$; merge sort is $\Theta(n \log n)$. The asymptotic verdict is unambiguous and, for large enough n, correct. But asymptotic verdicts are about large enough n, and where the arrays are never large, the verdict is about a situation nobody is in.

Measured on this site, insertion sort’s comparison count crosses merge sort’s between n = 4 and n = 6 — very early, because merge sort is genuinely good at comparing. But the total memory traffic — reads plus writes — tells a different story, and the crossover there sits between n = 12 and n = 16.

This is the case that gets an essay to itself because it is more interesting than the usual telling. The lesson for the notation is narrower and still worth having: the class names who wins eventually, and “eventually” is doing an enormous amount of work in that sentence.

Real examples of the same shape are everywhere. Matrix multiplication has algorithms with exponents below 2.4, and essentially nobody uses them, because the constants are astronomical and the crossover points are beyond any matrix anyone multiplies. The best known algorithm for a problem and the algorithm worth writing are frequently different algorithms.

Why the notation exists anyway #

Having spent a thousand words on its limitations, it is worth saying plainly that asymptotic notation is one of the most useful ideas in the subject and the alternatives are worse.

The alternative is exact counts, and exact counts are unusable for comparison. Insertion sort on random input performs, on average, $\frac{n^2 + n - 2}{4}$ comparisons — for a specific model of “random” and a specific way of counting. Change either and the formula changes. Nobody can hold a dozen such formulas in mind, and comparing two of them means comparing two polynomials, which mostly means looking at the leading term. Which is the classification.

The notation is a deliberate discarding of detail so that the remaining thing is comparable across implementations, machines, languages and decades. It works. Merge sort was $\Theta(n \log n)$ in 1945 and it is $\Theta(n \log n)$ now, and the fact survived a complete revolution in what a computer is. Almost nothing else about the analysis of a 1945 algorithm survives that.

What it costs is that the discarded detail is sometimes the answer. The discipline is knowing which situation applies.

Three sentences that sound like each other #

Worth separating, because the difference is where most confusion lives.

Merge sort is $\Theta(n \log n)$.

A claim about how the comparison count grows, in the limit, up to constants. Provable, proved, and true.

Merge sort takes $n \log n$ time.

Not a claim anyone should make. The time depends on the machine, on where the data is, on what else is running. The count and the time are related by a factor that is not remotely constant — the same algorithm on the same machine can vary by an order of magnitude depending on whether its working set fits in cache.

Merge sort is faster than heapsort.

A claim about two implementations on some data on some machine. It might be true. It is not implied by anything in the first sentence, and it needs its own measurement.

The slide from the first to the third happens constantly, usually in a single paragraph, usually without anyone noticing.

The four things the classification leaves out #

Given an algorithm and a decision to make, the classification is the first of five useful facts and the least specific.

1. The class, per input distribution. Which is what the notation supplies.
2. The constant for the count that dominates the cost. Merge sort’s 0.838 comparisons per $n \log_2 n$ against heapsort’s 1.613 — a factor of nearly two that the class hides.
3. The distribution, not the average. Randomised quicksort’s mean at n = 512 is about 4,900 comparisons and its worst over six hundred runs is meaningfully higher; the tail is what happens on the bad day and an average conceals it entirely.
4. The memory behaviour. Two algorithms in the same class with the same constant can differ by an order of magnitude in how much of their work reaches main memory.
5. Where the asymptotic regime starts. The class describes behaviour past some threshold and never says where the threshold is. Below that threshold, the class describes a situation nobody is in.

This site measures all five, and organises itself around the observation that only the first is conventionally reported.

What this site does instead #

The response here is not to abandon the notation. It is to keep it and to measure the things it discards.

Every algorithm declares a class per input kind. The declaration is then fitted against measured counts and granted only if the fit holds — so the class is a claim that can fail, rather than a label. The constant falls out of the fit and is reported. The input kind is always named. The range over which the fit was taken is always named, because a fit over one range and a fit over another can disagree, and on this site they have.

And a second, independent quantity is carried alongside, because the comparison count is not the running time and pretending otherwise is where most of the trouble starts.