Randomized Algorithms — Why Rolling Dice Makes Things Faster

Why does adding randomness make an algorithm faster? We build up quicksort with a random pivot, the one-sided error of Bloom filters, and the Monte Carlo / Las Vegas split from zero background — ending with the ways mishandled randomness actually breaks systems in production.

An analogy: you can always beat someone who always throws rock

If your opponent throws rock in every single round of rock-paper-scissors, you win every time. When their move is fixed, the move that beats it is fixed too.

Algorithms end up in exactly that position. A quicksort hard-coded to take the first element of the array as its pivot hits its worst case the moment you hand it an array that is already sorted. Every partition leaves one side empty, so you get $n$ partitions with close to $n$ comparisons each: $O(n^2)$ in total. And "already sorted" is one of the most common shapes real data takes — rows pulled with ORDER BY, logs in timestamp order, the output of the last sort. This isn't bad luck. The weak spot sits at a fixed address, in the input.

A randomized algorithm rolls dice at this point. Pick the pivot uniformly at random every time. Now the same input handed over a thousand times will not reproduce the same slowness, because what determines the speed is no longer the input — it's the die you rolled.

The intuition: relocating the worst case

This is the single idea at the center of randomization: move the worst case out of the space of inputs and into the space of random choices.

Complexity came in two flavors (complexity basics): worst case, a guarantee that holds for every input, and average case, an average taken over some assumed distribution of inputs. The weakness of the average case is that assumption itself. Real data is not drawn at random — it arrives sorted, reversed, full of repeated values — and an adversary can deliberately hand you the worst input there is.

What a randomized algorithm gives you is a third kind of guarantee: expected running time.

Or in words: whatever data somebody hands you, the average time the run takes stays under that ceiling.

$T(x)$ is the running time on input $x$, $\mathbb{E}$ means average, and $n$ is the input size. Read aloud: for every input whatsoever, the average running time is at most $f(n)$. The decisive detail is what the average is taken over — not the inputs, but the coins the algorithm itself flipped. Nothing is assumed about the input distribution, so the bound doesn't collapse no matter who is on the other end. An attacker can read my source code; they cannot read which numbers my generator will produce today. That sentence connects directly to the attack on hash tables we'll get to later.

Quicksort: why a random pivot works

The change is one line. Stop taking the pivot from the front and draw it uniformly at random from the current range.

To see why that speeds things up, count comparisons. The two elements that end up in positions $i$ and $j$ of the sorted array are compared directly only when one of them is chosen as a pivot. And among the $j-i+1$ elements that lie between them, the moment some third element is picked as pivot first, those two are split into different ranges and never meet again. So a comparison happens exactly when the first pivot drawn from those $j-i+1$ elements is $i$ or $j$ — probability $2/(j-i+1)$. Now just sum over all pairs.

A line which says: add up the odds of meeting over every pair of elements, and the total work lands at roughly the element count times its digit count.

$C_n$ is the total number of comparisons and $H_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ is the harmonic number (a quantity that grows ever more slowly and tracks $\ln n$). Put plainly: about 1.39 times the theoretical floor $n\log_2 n$ for comparison-based sorting — a 40% surcharge. Against the $n^2/2$ worst case of a fixed pivot, that gap widens by orders of magnitude as $n$ grows.

The worst case has not disappeared. Draw the smallest remaining element every single time and you are back to $O(n^2)$. But the odds of that, even for a hundred elements, sit far below winning the lottery. It can happen; nobody has a way to make it happen. That is what "relocated into the space of random choices" actually buys you.

Incidentally, mergesort is also $O(n\log n)$, so why is quicksort the one people reach for? Two reasons: it sorts in place without allocating a second array, and it walks contiguous memory front to back, which is friendly to the cache. Equal orders of growth, wildly unequal measured times — the appeal of randomization here rests partly on that constant factor.

From here we look at what this same idea turns into outside of sorting: the style that occasionally gets the answer wrong in exchange for being dramatically cheap, the style that is always right but whose runtime you can't predict, the Bloom filter as the flagship of the former, why randomization is the only thing that survives the curse of dimensionality, and the accidents that happen when randomness is mishandled in production.