Tolerance — where it appears
Named by 4 essays across 3 fields — each of them below, with the objects they name alongside it.
Fitting a class to measurements
A complexity class is normally read off the shape of the loops and written down. Here it is fitted to counts taken across three orders of magnitude, and an algorithm is granted a class only if the fit holds — which turns a statement about code into a statement that can fail.
A limit is not a prediction
Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.
Two pivots and what they cost
Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.
The period that is not a promise
Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.
Named alongside it
The objects these essays reach for when they reach for this one.
CutoffFalsificationQuicksortAmortised analysisAsymptotic analysisClosed formComplexity classCompression scheduleCounting conventionCurve fittingDual-pivot quicksortExtrapolation