A limit is not a prediction

This site measures operation counts and fits complexity classes to them. It is worth being exact about what that procedure can and cannot establish, because the machinery is persuasive and the persuasion outruns the logic.

A finite set of measurements cannot establish an asymptotic claim. Not with more data points, not with a wider range, not with a better fit. The claim $f(n) = \Theta(g(n))$ is about the behaviour of $f$ as $n \to \infty$, and every measurement stops somewhere. Infinitely many functions agree with any finite sample and diverge from each other beyond the last point. Choosing between them is not something the sample can do.

This is not a philosophical quibble to be acknowledged and set aside. On this site it happened, in the ordinary course of building the thing, to an algorithm whose class everybody already knows.

Why no amount of data settles it #

The logical point is worth stating carefully, because it is easy to nod at and then forget.

Suppose an algorithm’s counts have been measured at every size up to a million and they fit $n \log n$ beautifully. Consider the function that equals this algorithm’s count everywhere up to a million and equals $n^2$ thereafter. It agrees with every measurement taken. It is a different asymptotic class. No further measurement below a million distinguishes them, and measuring above a million just moves the problem.

That construction is artificial, but the real cases are not. Every algorithm with a threshold in it — a cutoff, a fallback, a precomputation that pays for itself only above some size, a data structure that switches representation when it grows — has exactly this shape, and the threshold is often far above where anyone measures. The insertion-sort cutoff every production sort implements is a threshold of this kind, and it is the reason the hybrid’s counts do what they do above.

There is also a mundane version of the problem that has nothing to do with infinity. Measurements stop somewhere because of resources, and where they stop is decided by the slowest algorithm in the comparison. This site’s fits run from n = 32 to n = 4,096 largely because selection sort at n = 100,000 is five billion comparisons — about a minute of build time for one point on one curve. The range is a budget decision, and budget decisions constrain conclusions.

The case #

Merge sort with an insertion-sort cutoff is $\Theta(n \log n)$. This is not in doubt: the recursion is the same as merge sort’s above the cutoff, and below it a bounded amount of insertion sorting happens on each of $n/c$ subarrays, contributing $\Theta(n)$. The sum is $\Theta(n \log n)$ and the proof is two lines.

The site’s algorithm table originally declared exactly that, for all four input kinds. On three of them the fit granted it. On reversed input the fit refused, and the refusal was correct.

Fitted from n = 64 to n = 4,096, the counts on reversed input match:

Linear wins. Both are outside the tolerance of 1.6, so neither is granted — but the ranking is unambiguous, and if the tolerance had been 1.75 the site would have confidently labelled a linearithmic algorithm as linear.

Fitted from n = 64 to n = 65,536:

The ranking reverses. Nothing about the algorithm changed. Nothing about the measurement method changed. The range changed.

Why it happens #

The hybrid’s comparison count on reversed input is a sum of two terms of roughly the shape

$$a \cdot n \cdot c + b \cdot n \log_2 \frac{n}{c}$$

where $c$ is the cutoff. The first term comes from the insertion sorting, the second from the merging. On reversed input the insertion phase is at its worst — a reversed subarray is insertion sort’s catastrophe case, costing $c^2/2$ per subarray — so the first term is large. The second is small, because merging two ascending runs where every element of one exceeds every element of the other terminates early.

So below a few thousand elements the linear term dominates, and the total is genuinely close to linear. The logarithmic factor only asserts itself once $\log_2(n/c)$ has grown enough to matter, which on this data happens somewhere past n = 10,000.

Neither term is an error. The function really does look linear over one range and linearithmic over a wider one, because it is a sum of a linear thing and a linearithmic thing and the crossover is where it is.

What the fit did about it #

Refused to grant a class, and stopped.

That is the correct behaviour and it is worth dwelling on what the alternatives would have been. The site could have granted $n \log n$ on the grounds that the proof says so — but then the fit is not testing anything, it is decorating a conclusion arrived at some other way, and it would have granted $n \log n$ to a broken implementation equally happily. It could have granted $n$ on the grounds that the measurement says so — but the measurement is a measurement over a range, and extending the range changes it.

What it does instead is decline. The algorithm table has no declared class for the hybrid on reversed input. The gate does not test one. An essay says why.

The cost of that is small: one missing label among about forty algorithm-and-input pairs. The benefit is that every other label on the site is a claim the measurements actually support.

The same phenomenon, in a formula #

Complexity classes are not the only place where a limit gets mistaken for a prediction, and the clearest example on this site is in a closed form rather than a class.

The expected number of probes to insert a key into a hash table under linear probing, at load factor $\alpha$, is

$$\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$$

This is Knuth’s result and it is exact — in the limit as the table size goes to infinity. Applied to a table of a particular size it is an approximation, and the error is measurable.

At $\alpha = 0.95$ and 256 slots, the measured mean is 48% below the formula. At 32,768 slots the discrepancy is a few percent. The condition under which the asymptotic form is trustworthy is roughly $m(1-\alpha)^3 \gg 1$, and at 256 slots and $\alpha = 0.95$ that product is 0.03 — nowhere near the regime the formula describes.

Somebody sizing a hash table by that formula at high load would over-provision substantially, and would be doing so on the authority of a correct theorem applied outside its range. The essay on the probe formula works through the whole comparison.

How far the measurement would have to reach #

The hybrid’s two terms can be separated by counting them separately — the comparisons spent inside the insertion-sort base cases, and the comparisons spent in the merges — which turns “the linear term dominates below a few thousand” from a plausible story into an arithmetic one.

Measured at cutoff 16 over eight seeds, the insertion term is $4.533\,n$ and the merge term is $0.990\,n\log_2(n/16)$. The insertion coefficient is flat to three significant figures from $n = 64$ to $n = 262{,}144$, which is what a genuinely linear term looks like. Setting the two against each other:

The last row is the point. For the $n \log n$ term to dominate this algorithm’s cost by two orders of magnitude — which is roughly what “asymptotically linearithmic” invites a reader to picture — the input would have to contain around $10^{139}$ elements — some fifty-nine orders of magnitude more than the number of atoms in the observable universe. Even the modest tenfold row asks for $10^{15}$ elements, which is a thousand times the largest array anybody has ever sorted.

The asymptotic statement is still true. Every one of those rows is a finite $n$, the ratio grows without bound, and the limit is exactly what the theorem says it is. What the table shows is that the limit is reached so slowly that no measurement anyone could take would ever see it, and a class describing behaviour nobody can reach is a class describing nothing about the algorithm as run.

This is also why the fit’s refusal is the right answer rather than a shortcoming. Over $n = 64$ to $4{,}096$ the linear term is the larger one, and a fit that reported $n\log n$ there would be reporting the asymptotics instead of the data. Over $n$ to 65,536 the merge term has pulled ahead and the fit reports the other class. Both answers describe their range correctly; neither describes the algorithm, because the algorithm does not have one shape.

The range where measurement fails is set by a tuning constant #

The separated terms above invite an arithmetic that the essay’s own case makes urgent: the crossover is not a property of the algorithm. It is a property of the cutoff, and the cutoff is a number somebody typed.

Write the insertion term as $a(c)\,n$ and the merge term as $0.990\,n\log_2(n/c)$. The two are equal when

$$\log_2 \frac{n^*}{c} = \frac{a(c)}{0.990}$$

which at $c = 16$ and $a = 4.533$ gives $n^* = 382$ — the measured 380, recovered from the coefficients rather than read off the plot. The interesting part is what happens when $c$ moves. On reversed input a base case of length $c$ costs about $(c-1)/2$ comparisons per element, so $a$ grows linearly in $c$, and it sits in an exponent. Doubling the cutoff therefore squares the ratio $n^*/c$.

Put numbers on that. At $c = 32$ the crossover moves from a few hundred elements to somewhere near twenty thousand. At $c = 64$ it is past ten million. A production sort using a cutoff of 32 — an entirely ordinary choice, and larger cutoffs are common — would, on reversed input, spend more comparisons in its insertion phase than in its merges across every array size this site fits over, every size most benchmarks reach, and a good deal beyond.

So the situation this essay documents is not a curiosity found at one setting of one parameter. It is the normal configuration, and the parameter that decides how far it extends is the one nobody thinks of as affecting complexity at all. The cutoff is chosen for cache behaviour and constant factors, exactly as a growth factor is, and its effect on which class the algorithm appears to be in over any reachable range is exponential in the value chosen.

Two consequences follow, and they pull in opposite directions.

The first is that the fit’s refusal is more robust than one bad range. Extending the measurement to 65,536 reversed the ranking at $c = 16$; at $c = 32$ it would not have, and at $c = 64$ no measurement anyone could run would. A reader tempted to answer “measure further, then” should notice that the distance to measure is set by an implementation detail and can be moved out of reach by changing it.

The second is that the honest description of such an algorithm names the cutoff. “Merge sort with an insertion-sort cutoff is $\Theta(n\log n)$” is true and says nothing about the object that runs; “at cutoff 16 the linear term dominates below about 380 elements, and at cutoff 64 below ten million” says what the code does. That is the same demand a threshold somebody chose makes of a streaming structure — a constant that appears in a loop condition rather than in a guarantee still decides the behaviour, and it is invisible in the notation precisely because the notation was built to discard it.

The same disagreement, three more ways #

The gap between the closed form and the count is the whole subject, so it is worth reading over more loads, more trials and fewer.

Extending the axis rather than filling it is the other direction, and it is the one that says how far the disagreement goes.

Filling the axis in is the third variation: the same four loads over twice the trials, so that the points settle without the shape moving.

What measurement can do #

Having established what it cannot do, the positive case is worth stating precisely, because it is not nothing.

Refute. If an algorithm claims $\Theta(n \log n)$ and its counts fit $n^2$ with a spread of 1.03 across three decades, the claim is wrong, or the implementation is wrong, or the input assumption is wrong. One of those, definitely, and finding out which is worth doing. Refutation is logically available to finite evidence in a way that confirmation is not — a single counterexample settles a universal claim, and no quantity of confirming instances settles it the other way. This asymmetry is the whole reason the site’s fitting machinery is worth building.

Measure the constant. The factor the notation discards is a finite quantity and finite measurement is exactly the right tool for it — as is the distance from an algorithm to its floor, which is a ratio between two numbers rather than a claim about a limit. Merge sort’s 0.838 comparisons per $n \log_2 n$ is a real number obtained honestly.

Catch the gap between the proof and the code. A proof about a recurrence is about the recurrence. The measurement is of the program that will actually run. Where they diverge — a bug, an accidental copy, a base case firing more often than expected — the measurement notices and the proof does not. This is not a criticism of proofs; it is a description of what they are about.

Show where the asymptotic regime begins. This one is undervalued. Knowing that an algorithm is $\Theta(n \log n)$ is less useful than knowing that its counts do not look linearithmic until n is past ten thousand. That threshold is measurable, it is exactly what asymptotic notation is silent about, and for anyone whose n is small it is the only part that matters.

What it looks like when the limit behaves #

None of this means closed forms and asymptotic classes are unreliable in general. Some of them are extremely well behaved, and the difference between the two situations is itself measurable.

Stirling’s approximation to $\log_2(n!)$ is the good case. The exact value — summed logarithm by logarithm — and the closed form agree to better than five parts in ten million at every size this site uses, including n = 8. There is no regime where using the closed form would mislead anyone about anything, and the site uses it as an independent check on the exact sum rather than as a substitute for it.

The probe formula is the bad case, and the difference between them is not that one is a better approximation in some abstract sense. It is that Stirling’s error term is $O(1/n)$ while the probe formula’s error depends on $m(1-\alpha)^3$, which stays small precisely in the regime — high load — where people most want the answer.

The lesson is not “distrust asymptotics”. It is: the size of the error is a separate question from the correctness of the limit, and it has an answer. For any closed form worth relying on, the error at the size in question can be measured, and measuring it takes an afternoon.

Two things this site does about it #

States the range on everything. Every fitted class here carries the range it was fitted over, every constant carries its input distribution, and no figure claims that its measurements say anything about sizes it did not measure. This is cheap and it is not standard.

Declines to label when the measurements do not support a label. Two of roughly forty algorithm-and-input pairs on this site have no declared class, and this essay is about one of them. The other is bubble sort on nearly sorted input, where neither linear nor quadratic fits — the count is $n$ times a slowly growing factor, and no candidate class describes it within tolerance.

The temptation in both cases was to round to the answer the reader expects. Resisting it costs two labels and buys the credibility of the other thirty-eight.

The honest statement of what this site is doing #

Every page here that reports a fitted class is reporting that a set of measurements over a stated range is consistent with that class, and that the alternatives are not. That is a weaker statement than a proof and a stronger one than a glance at the loops.

Where a proof exists — as it does for merge sort, for the comparison-sorting floor, for the amortised bound on a doubling array — the proof is the reason to believe the claim and the measurement is a check on the machinery. Where a proof exists but the implementation might not match it, the measurement is checking the implementation. And where the measurement disagrees with the expected answer, as it did twice during this site’s construction, the disagreement is the most valuable output the whole apparatus produces.

The one thing it never does is claim that measuring further would settle a question about infinity. That question is not the kind of thing measurement settles, and the case in this essay is the site’s own demonstration of why.