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.

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.