Fitting a class to measurements

Ask how anyone knows that merge sort is $\Theta(n \log n)$ and the answer is the recurrence. $T(n) = 2T(n/2) + n$, apply the master theorem, out comes $n \log n$. It is correct, it is a proof, and it is about the recurrence rather than about the code that will run.

The gap between those two things is where the bugs live. A merge sort with an off-by-one in its merge loop has the same recurrence and the same proof and does not sort. A merge sort that accidentally copies the whole buffer on every recursive call has the same top-line class and does far more work. Nothing about reading the loops distinguishes these from the correct implementation, because reading the loops is how the class was arrived at in the first place.

So on this site the class is not read off the code. It is fitted to the counts the code produces.

Why a slope is not enough #

The obvious method is to take logarithms of both axes and fit a straight line. The slope is the exponent, and the exponent names the class.

It half works. Fitted this way across n from 32 to 4,096 on random input, the site’s algorithms report:

The quadratic algorithms come out at 2.00, which is exactly right and satisfying — and worth pausing on, because nothing about being quadratic makes three algorithms interchangeable. The linearithmic ones come out around 1.2, which is not 1 and not any other round number, and that is the problem.

$n \log n$ is not a power law. It has no exponent. Fitting a straight line to it on log–log axes produces the average slope over the fitted range, which is $1 + \frac{1}{\ln n}$-ish and therefore drifts downwards as the range moves right. Fitted from 32 to 4,096 merge sort gives 1.213; fitted from 4,096 to 262,144 it gives something smaller. The number is real, it is reproducible, and it is not a property of the algorithm.

So the exponent is worth reporting — it cleanly separates the two families, and the gap between 1.25 and 2.00 is a chasm nothing falls into — but it cannot be the test.

Where the measurements are taken #

Two decisions have to be made before any fitting happens, and both affect the answer.

The spacing. Sizes are spaced evenly on a logarithmic scale — 32, 54, 91, 152, 256, and so on — rather than evenly on a linear one. Linear spacing puts almost all the measurements at the large end, where the curve is nearly straight on log–log axes and every candidate class looks alike; log spacing puts equal weight on each decade, which is where the classes actually separate. The same reasoning is why the plots have logarithmic axes in the first place.

The range. Three orders of magnitude is the standard used here, and it is a compromise. Too narrow and everything fits everything: over a single doubling, $n$, $n \log n$ and $n^{1.2}$ are indistinguishable to any tolerance worth having. Too wide and the quadratic algorithms become unaffordable — selection sort at n = 100,000 is five billion comparisons, which is a minute of build time for one point on one curve.

The ratio test #

The test used here is simpler and stronger. For a candidate class $f(n)$, compute $c_i = \frac{\text{count}(n_i)}{f(n_i)}$ at every measured size, and look at how much $c$ varies.

If the algorithm really is $\Theta(f)$, then $c$ is bounded above and below by constants — that is precisely what $\Theta$ means — and across a range of sizes it should be roughly flat. If it is not, the ratio will drift monotonically in one direction and keep drifting.

The measure used is the spread: the largest $c$ divided by the smallest. A perfect fit has spread 1. The tolerance is 1.6, meaning the ratio may vary by up to 60% across three orders of magnitude before the class is refused.

Applied to merge sort’s counts against the six candidate classes:

That is not a close call. The correct class sits at 1.21 and the nearest wrong one at 2.91, a margin of nearly two and a half, and against the class it is most often confused with — quadratic — the margin is a factor of thirty-six.

Choosing the tolerance honestly #

A tolerance chosen to make the tests pass is not a test. The number has to sit between two things that are themselves measured: the noise, and the smallest real failure.

The noise. A correct fit is not exactly flat, for reasons that have nothing to do with being wrong. Lower-order terms are real: merge sort’s cost is $n \log n$ plus terms in $n$, and at n = 32 the lower-order terms are a substantial fraction of the total while at n = 4,096 they are not. Recursion base cases, integer rounding when a range is split, and the specific input all contribute. Across every class this site grants, the observed spreads run from 1.02 to 1.45.

The smallest real failure. The tightest non-fit available is not a wildly wrong class — those come in at three, forty, hundreds — but one of the two claims the fit refused. Bubble sort’s counts on nearly sorted input miss the linear class at 1.79, and the hybrid’s counts on reversed input miss $n \log n$ at 1.99.

The tolerance is 1.6, and it sits between 1.45 and 1.79. Those margins are not large, and pretending otherwise would be the same failure this whole method exists to avoid: the honest description is that the tolerance separates the cases measured here with a little room on each side, and that a genuinely marginal case would come down to a judgement the number cannot make on anyone’s behalf. Both margins are checked on every build, so loosening the tolerance enough to grant bubble sort linearity would break the check rather than quietly pass it.

The fit has to refuse things #

An acceptance test that accepts everything is not a test, and this is the failure mode that hides best: everything downstream is written as though the check were working.

So the site’s gate does not only require the correct classes to be granted. It requires the wrong ones to be refused, explicitly and by name:

• selection sort’s counts must fail the $n \log n$ fit
• merge sort’s counts must fail the linear fit
• insertion sort’s claim of linearity, true on sorted input, must fail on random input

If any of those started passing, every caption on the site would be unearned and nothing else would notice, because every figure would still draw a perfectly plausible curve.

Two claims the fit refused #

The mechanism only earns its place if it is capable of contradicting the person who built it. During construction it did so twice, and neither refusal was a bug.

Bubble sort on nearly sorted input. Bubble sort with the early-exit optimisation is widely described as linear on nearly sorted data, and the site’s algorithm table originally declared it quadratic there on the grounds that the optimisation cannot help enough. Measured, neither is right. Across n from 64 to 65,536 the counts divided by $n$ vary by a factor of 1.84 and divided by $n^2$ by a factor of 747. Linear is much closer and still outside tolerance.

The reason is structural, and it is the same reason adaptivity resists a clean classification generally. Bubble sort’s cost is roughly $n$ times the number of passes, and the number of passes needed depends on how far the most displaced element has to travel. In the site’s nearly-sorted generator the number of displaced elements is proportional to n, so the maximum displacement grows slowly with n too, and the cost is $n$ times something that creeps upward. No clean class describes it, and the fit says so.

The hybrid on reversed input. This one is sharper and gets its own essay. Merge sort with an insertion-sort cutoff, measured from n = 64 to n = 4,096 on reversed input, fits linear better than $n \log n$ — spread 1.69 against 1.92. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range.

Both claims were withdrawn from the algorithm table. That is what the machinery is for, and the alternative — adjusting the declaration to whatever the audience expects — would have made every other declaration on the site worthless.

It is worth noticing what each refusal cost. Neither algorithm changed. Neither is worse than it was. All that happened is that the site now declines to attach a two-symbol summary to two of the roughly forty algorithm-and-input pairs it measures, and says instead what the counts do. That is a small price, and the alternative price — every other declaration being a matter of taste — is not small at all.

What the fit does not do #

It does not prove anything.

This bears repeating in the middle of an essay about fitting, because the machinery is persuasive and the persuasion outruns the logic. A fit over three orders of magnitude establishes that the counts are consistent with a class over that range. Infinitely many functions are consistent with any finite set of measurements and diverge from each other beyond the last data point. No amount of measuring settles the question of what happens at infinity, which is the only question $\Theta$ is about.

What the fit can do is refuse. If an algorithm claims $n \log n$ and its counts fit $n^2$ with a spread of 1.03 across three decades, something is wrong — the claim, or the implementation, or the input assumptions — and finding out which is worth the trouble. Refutation is logically available to finite measurement in a way that confirmation is not, and the site’s machinery is built to exploit exactly that asymmetry.

There is a second thing it can do, which is to catch the discrepancy between what an implementation is supposed to be and what it is. This is the case the proof genuinely cannot reach. A proof about a recurrence establishes something about the recurrence; the fit is measuring the code that will actually run, and where those two diverge — because of a bug, an unintended copy, a base case that fires more often than expected — the measurement notices and the proof does not. That is not a criticism of proofs. It is a description of what they are about, and what the floors field does with the ones that are genuinely about every possible algorithm is a different and stronger kind of argument again.

The constant comes free #

A useful side effect: once a class has been granted, the ratio $c$ is not just flat, it is a number. That number is the constant the notation throws away.

Merge sort’s comparison count divided by $n \log_2 n$ settles at 0.838. Heapsort’s settles at 1.613. Both are $\Theta(n \log n)$, and heapsort does 1.9 times as much comparing — while ranking the other way round on some counts and not others. That factor is invisible in the classification and is often the whole of what matters, which is why it gets an essay of its own.

The method in six lines #

1. Run the algorithm at sizes spaced evenly on a log scale, spanning at least three orders of magnitude.
2. For each candidate class $f$, compute $\text{count}/f(n)$ at every size.
3. Take the spread — largest divided by smallest.
4. The best-fitting class is the one with the smallest spread.
5. Grant the class only if that spread is under tolerance, and the tolerance sits demonstrably between the observed noise and the tightest real failure.
6. Report the constant, because it was computed on the way.

None of this is difficult, and none of it is standard. The reason seems to be that the class is usually known before anyone thinks to measure — and once the answer is known, measuring feels like a formality. It is a formality right up until the moment something disagrees, which is exactly when it was needed — and the disagreements worth having are rarely about whether an algorithm is quadratic. They are about how close to the floor it gets, and about the constant nobody wrote down.