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.

Two more sweeps say what the fit is a statement about. Change the input and the same four algorithms move class; change the range and they do not.

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.

A drift is not a wobble #

The spread is a range and a range throws away the one thing that separates a wrong class from a noisy right one: which way the ratio is moving.

A genuinely wrong class produces a ratio that drifts in one direction and keeps drifting, because the two functions have different growth and the gap between them widens without limit. Noise produces a ratio that moves up and down with no direction. Those look identical to a largest-over-smallest statistic and completely different on the plot.

So a sharper test is available: measure the trend rather than the range. Correlate the ratio against $\log n$ and ask whether the relationship is monotone. A class whose ratio wobbles by a factor of 1.7 with no direction is a class the range test refuses and the trend test grants; one whose ratio climbs steadily by 1.3 is the reverse.

That would tighten both of the marginal cases this essay reports. Bubble sort’s ratio on nearly-sorted input at 1.84 is not noise — it climbs at every step, because the number of passes creeps up with $n$ — and a trend test would refuse it more decisively than a range test at a threshold of 1.6.

There is a difficulty and it is the reason the site uses the blunter instrument. A correct class also produces a trend, because lower-order terms are real: merge sort’s cost is $n\log n$ plus terms in $n$, so its ratio against $n\log n$ falls monotonically as the lower-order terms become a smaller share. The trend is genuine and it is not evidence of a wrong class.

What distinguishes the two is whether the trend decays. A lower-order term’s contribution to the ratio shrinks like $1/\log n$ and the ratio approaches a constant; a wrong class’s contribution grows without bound. So the honest version of the trend test is a test on the second difference — is the drift flattening or is it not — and that needs more measured sizes than three orders of magnitude comfortably supply.

Which is why the site reports a range and states its margins rather than computing a trend and stating a p-value. The blunter statistic is defensible with the data available; the sharper one is the right instrument and would want a wider sweep than the quadratic algorithms can afford.

The best fit is best among the offered #

One more property of the procedure deserves stating, because step four says the best-fitting class is the one with the smallest spread and that sentence has a silent qualifier in it.

There are six candidates. The winner is the best of six, not the best of all functions, and if the true behaviour is not in the list then the procedure returns whichever of the six is least wrong — with a spread that may or may not clear the tolerance, and with no indication that the vocabulary was the problem.

That is not hypothetical on this site. Randomised selection’s consumption of random bits grows like $(\log n)^2$, which is not among the six; against the nearest offered class it lands at a spread of 1.98 and is refused, while against $(\log_2 n)^2$ it is flat to 1.14. The measurement is clean and the vocabulary cannot express it, so the class was withdrawn rather than granted — which is the right outcome and required somebody to notice that the refusal meant not in the list rather than not a class.

Two habits follow. A refusal is ambiguous — it says the counts do not fit any offered class, and the two reasons for that are a bad implementation and a short list. And the list should be reported alongside the verdict, because a reader who knows only that the fit refused everything cannot tell which of the two happened.

Enlarging the list is not free, either, and that is the reason it stays at six. Every extra candidate is another chance for a wrong class to fit by accident over a finite range, and the classes that are near-neighbours — $n\log n$ against $n^{1.2}$, say — are exactly the ones a three-decade sweep cannot separate. A small vocabulary of well-separated classes refuses more and mistakes less, and the price is a withdrawn claim now and then.

The same machinery, two variables #

The procedure above fits a class in one size parameter, and a graph has two. The extension is small and it needs one thing the one-variable version does not: a claim is granted only when the sweep can also be shown to distinguish it from a named alternative.

The reason is that with two parameters, a single sweep collapses candidates that are genuinely different. Sweep the number of vertices at a fixed average degree and $E$ is proportional to $V$, so $V$, $E$ and $V + E$ become one curve and all three “fit” at a spread of 1.00 — which is a fact about the experiment rather than about the algorithm. The graph field is built on that distinction, and the assertion that enforces it refuses a real case rather than an imagined one.