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 $n$ is, and why the answer is not obvious #

Before any of that there is a prior omission, and it is so basic that it is almost never mentioned: the notation does not say what $n$ counts.

For a sort, $n$ is taken to be the number of elements, and that is already a choice rather than a fact. The input is not $n$ things, it is $n$ values, and $n$ distinct values need $n \log_2 n$ bits to write down. An algorithm that reads its whole input once is therefore linear in elements and superlinear in bits, and the two statements are both correct and describe the same code. Which one is meant depends on a convention nobody states.

Charging one unit per comparison is the same kind of choice. It is a cost model, and it is a good one when the elements are machine integers. Sorting 200-byte strings, a single comparison walks up to 200 bytes, and the comparison count is then a count of variable-cost operations dressed up as a count of atoms. The class in the unit “byte comparisons” need not match the class in the unit “comparisons” — for strings drawn from a small alphabet it does not, because the expected number of bytes examined per comparison depends on how many keys share a prefix, and that depends on $n$.

The problem gets sharper the moment a problem has two size parameters. A graph has $V$ vertices and $E$ edges, and a bound like $O(E \log V)$ has no order relation to $O(V^2)$ until the density is stated: on a sparse graph the first is far smaller and on a dense one it is larger. Two algorithms with published bounds can each be the better choice, and the published bounds do not say which is which. That is a whole field on this site rather than a footnote, because it is where the habit of comparing bounds instead of measurements does the most damage.

The same ambiguity hides in almost every non-sorting bound. String matching has a pattern length and a text length. A hash table has a capacity and an occupancy, and the interesting bounds are in the ratio rather than in either. A matrix algorithm has rows, columns and non-zeros. In each case “$O(n)$” is a statement waiting for someone to say which $n$.

This site’s answer is procedural rather than clever. Every figure that reports a count says which operation it counted, in the strip along its bottom edge; every fit names the input kind and the range of sizes it was taken over; and where a bound has two parameters, the density regime is stated before the class means anything. None of that makes the notation better. It makes the missing arguments visible.

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.

The symbol is not an equals sign, and the algebra is not algebra #

There is a second family of misuse, separate from the constants and the threshold, and it comes from the notation looking like arithmetic when it is not.

$f(n) = O(g(n))$ is a membership statement wearing an equality’s clothes. The right-hand side is a set of functions, the left is one function, and the claim is that the function is in the set. So the symbol does not commute. $O(n) = O(n^2)$ is true, in the sense that every function bounded by a multiple of $n$ is bounded by a multiple of $n^2$; $O(n^2) = O(n)$ is false. An equals sign that reads correctly in one direction and falsely in the other is not an equals sign, and every trap below is a consequence of treating it as one.

Bounds do not subtract. If two algorithms are each $O(n^2)$, the difference between their costs is not $O(1)$ and not $O(n)$ — it is $O(n^2)$, and the notation has no way to express that one is smaller. This is the formal statement of why a comparison between two published bounds is not a comparison between two algorithms.

Bounds do not accumulate under a sum unless the constant is uniform. Writing $\sum_{i=1}^{n} O(i) = O(n^2)$ is only valid when a single constant works for every term. If the constant may grow with $i$ — which is exactly what happens when the “$O(1)$ step” is a hash-table operation whose probe count depends on the occupancy, or a comparison whose cost depends on how many keys share a prefix — the sum is not bounded by any of the terms’ bounds. The fallacy has a standard form: each of the $n$ operations is $O(1)$, so the whole thing is $O(n)$, said about $n$ operations that were never uniformly bounded.

And $O$ is a partial order, not a total one. This is the deepest of the three and the least often stated. Two functions can be incomparable — neither is $O$ of the other — and it is not a pathology of contrived oscillating functions. It is the ordinary case for a problem with two size parameters, which a whole field here is about: $E\log V$ and $V^2$ have no order relation, so the question “which algorithm has the better bound” has no answer at all until a density is named. The bound was never incomplete; the ordering does not exist.

$\Theta$, by contrast, is an equivalence relation — reflexive, symmetric, transitive — so it genuinely partitions functions into classes, which is what people are reaching for when they say two algorithms “have the same complexity”. That is the other reason the two-sided ratio test above is worth its extra strictness: it grants a statement one can reason with, rather than one that only points in a direction. And it is why naming the model a bound was quoted in is not pedantry either — the class, the parameters and the unit have to be fixed before the symbol denotes anything at all.

The same four algorithms, four ways #

The classification is a statement about a curve, and the curves are cheap to draw — so they are drawn on three more inputs and over a wider range.

Reversed input is the other end of the same axis, and the notation gives insertion sort one symbol for both ends of it.

The other two variations hold the input fixed: one extends the range, and one drops the algorithm whose class is in question so the rest can be read against each other.

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.