What derandomising costs

Selection — finding the $k$-th smallest element without sorting — has a randomised algorithm everybody uses and a deterministic one everybody teaches. Both are $\Theta(n)$. The deterministic one is famous for being the answer to “but what if the coin flips go badly”, and it is famous for not being used.

The usual explanation is that its constant is bad. That is true and it is not the interesting part, because the constant is only 2.54 and a factor of 2.54 is not why an algorithm goes unused. The interesting part is what the 2.54 buys, which is not the worst-case guarantee people describe it as buying.

The two algorithms #

Randomised quickselect. Pick a pivot uniformly at random from the current range, partition, and recurse into whichever side contains the target. The expected number of comparisons is $2n(1 + \ln 2) \approx 3.39n$ for the median, and the derivation is a short recurrence. On any input.

Median of medians, from Blum, Floyd, Pratt, Rivest and Tarjan. Split the range into groups of five, sort each group, take the median of each group, and recursively select the median of those medians; use that as the pivot. The pivot is then guaranteed to be between the 30th and 70th percentiles, so the recursion shrinks by at least 30% every time and the total is $\Theta(n)$ in the worst case — deterministically, with no coins anywhere.

Both are linear. The difference in the class is what the linearity is a statement about: for the first it is an expectation over the coins, and for the second it is a bound over every input.

What forty seeds say #

The measurement is thirty to forty independent runs at each size, because one run of a randomised algorithm is an anecdote and this is the algorithm where that bites hardest.

Three results, and the third is the one this essay is about.

The constants are 3.21 and 8.15, averaged over forty seeds at $n = 20{,}001$. The randomised measurement lands close to the theoretical $3.39n$; the deterministic one is 2.54 times it. Both are honestly linear over the range measured.

The deterministic rule spends zero random bits, which is a measurement here rather than a remark about the source code, because the site counts them. The randomised rule spends 246 per run at $n = 20{,}001$ — a small number, and not zero.

And the spreads are 27.7% and 1.6%. That is the finding. The randomised algorithm’s cost on identical data varies by a factor of three depending on nothing but the seed; the deterministic algorithm’s barely varies at all, and what variation it has comes from the data rather than from anything internal.

Where the 8.15 comes from #

A constant of 2.54× is worth accounting for, because the components are visible in the algorithm and the total is a check on whether it is implemented as described.

Per level of the outer recursion on a range of size $s$, median-of-medians does three things:

Sorts $s/5$ groups of five. Insertion sort on five elements averages about 7.7 comparisons, so this is $7.7 \times s/5 \approx 1.54s$. This is the largest single component and it is the reason groups of five rather than three: groups of three make the guaranteed split too weak for the recursion to be linear at all, and groups of seven cost more per group than the tighter split saves.

Selects the median of the $s/5$ medians, recursively. By the same accounting that is about $2.5 \times s/5 = 0.5s$ once the recursion is unrolled.

Partitions the range. $s$ comparisons.

That is roughly $3s$ per level. The guaranteed split is at worst 70/30 and is typically much better than the guarantee — the median of medians of a random array is usually close to the true median — so in practice the range roughly halves each level and the total is about $3s \times 2 = 6s$, plus the recursive median subproblems. The measured 8.15 is in that neighbourhood, and the gap between 8.15 and the 24 or so the worst-case analysis gives is the difference between the guaranteed split and the typical one.

So median-of-medians is, in practice, running at about a third of its own worst-case constant — which is itself a mildly interesting fact, because the whole point of the algorithm is that the worst case is bounded, and the bound it is famous for is three times what it usually costs.

Which is why the folklore is the wrong way round #

The standard framing is that median-of-medians is the safe choice and randomised quickselect is the fast one, with the safety being about the worst case — the vanishingly improbable run where every pivot is terrible.

That framing gets the risk in the wrong place. The worst case of randomised quickselect is $\Theta(n^2)$ and its probability is somewhere around $2^{-n}$; nobody has ever seen one and nobody ever will. What people actually experience is the measured distribution above: a run that costs 1.6 times the mean, which happens routinely, and which at 24.6% relative spread happens often enough to appear in any sample of a few dozen runs.

So the honest statement of the trade is:

• Not “randomised is fast and might be catastrophic”.
• But “randomised is 2.5 times cheaper on average and 60% more expensive than its own average on a bad day; deterministic is 2.5 times more expensive always, and always means always”.

Which of those two is preferable depends entirely on whether the thing being budgeted is throughput or latency. For throughput — total work over many operations — the randomised version wins outright, because the average is what accumulates and the average is 2.5 times better. For a tail latency target — a 99th percentile that must be met — the comparison is between the randomised algorithm’s 99th percentile and the deterministic algorithm’s flat cost, and at $n = 20{,}001$ those are 5.21 and 8.33 comparisons per element. The randomised one still wins, and by less.

Why the spread is so different #

The reason the two distributions are shaped so differently is worth a paragraph, because it generalises past selection.

Randomised quickselect’s cost is dominated by its first few pivots. The first partition costs $n$ comparisons whatever happens, and then the size of the remaining problem is decided by one draw. A first pivot at the 5th percentile leaves 95% of the array; one at the 50th leaves 50%. The whole rest of the run is scaled by that single decision, so the total is essentially a product of a handful of random factors and it has the variance of a product.

Median-of-medians has no such decision. Every pivot is guaranteed to be between the 30th and 70th percentiles, so the shrinkage per level is bounded on both sides and the total is a sum of tightly constrained terms. Its 1.6% residual variation is the data, not the algorithm.

The general rule this suggests, and which the skip list essay arrives at from the other direction: a randomised algorithm concentrates when its cost is a sum of many independent contributions, and does not when its cost turns on a few. A skip list search is a sum over $\log n$ levels and concentrates to 6%; a randomised selection is a product over a handful of pivots and spreads to 25%. Both have clean expected bounds. Only the first one’s bound is a prediction.

The measurement that nearly went wrong #

The assertion behind these numbers originally compared one randomised run against one deterministic run at $n = 20{,}001$, and demanded a factor of at least two.

It failed, at 1.40×. The randomised run had drawn a bad seed — 5.7 comparisons per element against its own mean of 3.2 — and the assertion concluded there was no price to derandomisation.

That is the same error the algorithm’s users make, made by a test: a single run of a randomised algorithm cannot support a statement about its cost, and an assertion that takes one is measuring the seed. Over forty seeds the two numbers separate cleanly at 2.54 and the assertion has never wobbled since. The rewritten version also checks the spreads, requiring the randomised rule’s relative standard deviation to be at least five times the deterministic one’s — which is the actual finding, and which the original assertion did not look at.

Worth noting what the failure did not look like. Nothing crashed, no figure drew wrongly, and the number 1.40 is perfectly plausible. Had the tolerance been set at 1.2 rather than 2, the assertion would have passed, the essay would have reported a 40% cost for derandomisation, and it would have been wrong by a factor of nearly two with no indication anywhere.

The other deterministic rule, and why it is not the answer #

There is a much cheaper deterministic pivot rule than median-of-medians, and it is the one real libraries actually reach for first: take the first element, or the middle one, or the median of three of them. Those cost essentially nothing and they are deterministic.

They are also not a derandomisation of anything. A first-element pivot on random input is indistinguishable from a random pivot — the figure above shows it sitting alongside the randomised rule, because when the data is random, taking a fixed position is taking a random element. What it lacks is the guarantee, and the lack shows up on exactly one input. At $n = 8{,}001$ on sorted data:

Three thousand comparisons per element, which is $n/2$ per element, which is the quadratic behaviour written out. The cheap deterministic rule is not a middle option between the other two; it is a fourth thing entirely, with the randomised rule’s constant on ordinary data and no bound at all on the input it cannot handle.

That is worth stating because “deterministic” covers both of the deterministic rules here and they have nothing in common. One has a proved worst-case linear bound and costs 2.5×; the other has no bound and costs nothing. Choosing “the deterministic one” is not a choice until which one is named.

What the deterministic algorithm is actually for #

Having spent the essay arguing that the folklore reason is wrong, here is the case for it that survives.

When the input is adversarial and the seed is not secret. The whole of the preceding essay is about how completely a randomised guarantee evaporates when the coins are known. A deterministic algorithm with a worst-case bound does not have that failure mode, because it has no coins to learn. In an environment where secret randomness is genuinely unavailable — some embedded systems, some formally verified contexts — median-of-medians is the answer and its 2.54 is the price.

When the bound has to be provable rather than measured. A real-time system certified against a worst-case execution time cannot use a bound that holds with probability $1 - 2^{-n}$, because the certification does not have a place to put the probability. This is a legitimate and narrow requirement and it is the one median-of-medians actually meets.

As the fallback half of a hybrid. Introselect — run randomised quickselect, and if the recursion depth exceeds a threshold, switch to median-of-medians — gets the randomised constant almost always and the deterministic bound always. That is what real libraries do, and it is the same shape as introsort’s depth limit: use the fast algorithm and keep the slow one as insurance that is almost never claimed on.

Why five, and the sweep that is not run here #

The group size is a parameter, it is always five, and the reason is arithmetic that the accounting above has most of the pieces for. It is worth assembling, because it explains why the constant is as large as it is and why it cannot be tuned down.

The recursion has two calls: one on the $n/g$ medians, and one on whatever survives the partition. Linearity requires those two fractions to sum to less than one — if they reach one, the recursion does the same amount of work at every level and the total is $\Theta(n\log n)$ rather than $\Theta(n)$.

With groups of $g$, the pivot is guaranteed to beat about half the group medians, each of which beats about half its own group, so roughly a quarter of the elements are eliminated and about three quarters survive. The median subproblem is $1/g$. So the condition is approximately

$$\frac{1}{g} + \frac{3}{4} < 1$$

which fails at $g = 3$ — a third plus three quarters is over one — and holds from $g = 5$ upward. That is the whole reason groups of three do not work, and it is a statement about a sum of two fractions rather than anything subtle about medians.

So why not seven, or nine? Because the term that grows is the group sort. Sorting a group of $g$ by insertion costs about $g^2/4$ comparisons, and there are $n/g$ groups, so the group-sorting work is about $ng/4$ — linear in the group size. Going from five to seven raises that term by 40% and improves the eliminated fraction only slightly, since the guarantee approaches a quarter and stops. Five is the smallest size that works, and because the dominant cost grows with $g$, the smallest size that works is also the cheapest.

That accounts for the largest component of the 8.15: the group sort alone is about $1.54n$ per level of a recursion several levels deep, and it is there because the algorithm needs a guaranteed median of each group rather than a sample of one.

None of the above is measured on this page. It is a derivation from the recurrence, offered because it says what the constant is made of and where it would move; a sweep over group sizes would be a genuine measurement and it is not run here, so the numbers for seven and nine are absent rather than estimated. What can be said from the measurements is that the total at $g = 5$ is 8.15 comparisons per element, and that the group sort is the largest single term inside it.

The constants at three sizes #

The two rules differ by a constant, and a constant is a claim about a sweep rather than about a size.

The third variation holds the size fixed and changes how many draws went into the picture, which is the parameter that decides how much of the randomised rule’s distribution is visible at all.

The honest limits #

Two, both about what the range of the measurement supports.

Linearity is fitted, not established. Both algorithms’ comparison counts are measured at 4,001 and 20,001 and fitted linear over that range. That is the site’s standing limit: a finite sample cannot establish an asymptotic claim, and what is being reported is that the counts are linear over the sizes measured, with the constants stated. The worst-case linearity of median-of-medians is a theorem and does not depend on the measurement; the expected linearity of randomised quickselect is also a theorem; what the measurement adds is both constants, which no theorem gives.

Forty seeds see nothing rarer than one in forty. The 27.7% spread and the maximum of 5.84 comparisons per element are properties of a forty-run sample. Whether randomised quickselect can produce a run costing ten times its mean is not a question forty runs answer, and the theory says the probability decays exponentially. So “the worst observed” is what the figures report, and the worst possible is not measured and is not claimed.

The shape of the result #

Set the phase’s two directions side by side, because this essay is the second one and the first is everywhere else in it.

Adding randomness to quicksort’s pivot, to a search tree’s balance, to a hash table’s bucket choice: costs almost nothing measurable — two bits per key, thirty-two bits per key, one multiply — and removes a catastrophic input each time.

Removing randomness from selection: costs 2.54 times the comparisons and removes a variance of 28%.

Both are worth doing in the right circumstances and neither is free, and the reason to have both numbers is that the circumstances are decided by which resource is scarce. What the measurement adds to the textbook account is that the second trade is not the one it is usually described as. Derandomisation is not sold as variance reduction and that is exactly what it is: the deterministic algorithm is slower on every input including the good ones, and what it buys is that the cost stops depending on anything outside the program’s control.