Why does choosing a partition pivot at random help when the worst case is still O(n^2)?

## Two different bounds wearing similar words **Worst case** is a maximum over inputs: the most expensive run the algorithm can have on any input of size n. **Average case** is an expectation over an assumed *distribution of inputs* — it says "if your data looks like this, expect that". **Expected cost of a randomized algorithm** is something else again: an expectation over the algorithm's own coin flips, taken *separately for every fixed input*. Confusing the last two is the single most common mistake in this area, and the entire value of randomization lives in the difference. ## Why a deterministic rule always has a killer input A deterministic pivot rule is a function from the input to a choice. It is written down, shipped and readable. Whoever wants to hurt you can therefore simulate it: feed a candidate input, see which element the rule picks, and arrange the data so that pick is maximally unbalanced — then repeat for the recursive calls. This works for any fixed rule, not just the naive ones. Choosing the first element, the last, the middle, or a fixed sample of positions all yield a constructible worst case; the construction just gets more tedious. And you do not need a hostile adversary for this to bite. The inputs that break simple deterministic rules are the inputs production generates by accident: rows arriving already sorted from an index scan, near-constant columns, reverse-ordered exports, batches assembled by appending yesterday's sorted output. A worst case that requires random data to hit is a footnote; a worst case that fires on sorted data is a latency incident waiting for a Monday. ## What randomization actually changes It does not lower the worst-case bound. The quadratic case still exists — it is the run where the coin hands you the most unbalanced split at every level, and it is available for every input. What changes is the **quantifier**. Before: "there is an input for which this is slow, and if your data resembles it, you are slow every single time." After: "for every input, the expected cost is good, and the slow runs require a specific unlucky sequence of draws that you will not see twice." The bad case stops being a property of the data and becomes a property of that run. It is insurance in the ordinary sense: the loss is still possible, but it is no longer correlated with something the world reliably supplies. The probability side is worth stating carefully. A run materially worse than the expected bound becomes rapidly less likely as n grows, and the genuinely quadratic extreme requires an unbroken run of terrible draws whose probability is astronomically small at any realistic size. But "unlikely" is not "impossible": if a hard bound is what you must promise, randomization is the wrong instrument and you need a different guarantee mechanism, which costs constant factors and complexity. ## The premium on the insurance Randomization is bought, not free. Every partition step spends a draw from a random source, and that source is a shared, sometimes contended resource. The constant factor goes up slightly, and in exchange the tail behaviour stops being input-dependent. That is a trade almost every production sort makes, and it is the honest way to present it to a skeptic: not "random is faster" — it is not — but "random is what makes the fast case unconditional". ## Where the protection stops Randomization defends only against an adversary who cannot predict the draws. Hardcode the seed, derive it from something guessable, or log the draw sequence somewhere reachable, and an input can be built against your actual coins. At that point you have a deterministic rule with extra steps and a worse constant. The corollary is an engineering discipline, not a cryptographic one for most workloads: keep the seed injectable, record it with the run, and treat it as an input. Fixed seeds in tests give reproducible assertions; varied seeds in a longer-running suite explore the distribution; a recorded seed in production makes a pathological run replayable instead of a ghost story. "It was slow once and we never reproduced it" is what unrecorded randomness costs. ## The contract this is an instance of A randomized-pivot pass is always correct — it only takes a variable amount of time to finish. That is one of the two standard contracts for randomized algorithms, the one that trades runtime certainty for correctness certainty. Knowing which contract you are buying is what lets you argue for randomization in a system with a latency budget: you are adding variance to a metric that operations already knows how to manage, and removing a correlation between input shape and disaster.