The pivot problem, and the fix
You already know plain quicksort from the divide-and-conquer rung: pick one element as the pivot, partition the array so everything smaller sits on its left and everything larger on its right, then recurse on the two sides. When the pivot lands near the middle every time, the array halves at each level, you get about log n levels of O(n) partitioning work, and the total is a beautiful O(n log n). But when the pivot is always the smallest or largest element, one side is empty and the other holds n-1 elements; the recursion becomes a tall thin chain of depth n, and the cost collapses to Theta(n^2). The painful part is that the disastrous case is not exotic — if you always pick the first element as pivot, an already-sorted array triggers exactly this worst case. The very input you would hope is easiest is the one that kills you.
The fix is almost insultingly simple: do not let the input choose the pivot — let a coin do it. Randomized quicksort picks the pivot uniformly at random from the current subarray each time. Nothing else changes; the partition step is identical. But now the running time stops being a fixed property of the input and becomes a random variable, because the algorithm itself makes random choices. There is no longer any single bad input. Whatever array you hand it — sorted, reversed, adversarially constructed — the distribution of pivots is the same, so the expected running time is the same. This is a Las Vegas algorithm from the first guide in this rung: the output is always a correctly sorted array; only the time it takes is random.
Counting comparisons with indicator variables
To bound the expected running time we count the one thing quicksort spends its time on: comparisons between elements. Here is the elegant trick that makes the whole analysis fit on a page. Sort the n elements in your head and call them z_1, z_2, ..., z_n in increasing order (the algorithm never sees this order; it is just for the proof). The key question is: for two particular elements z_i and z_j, what is the chance the algorithm ever compares them? In quicksort, two elements are compared if and only if one of them is chosen as a pivot while the other is still in the same subarray — once they are split into different sides by some other pivot, they never meet again.
Now focus on the block of elements z_i, z_{i+1}, ..., z_j — that is the j - i + 1 elements whose values lie between z_i and z_j inclusive. Whichever of these is picked as a pivot FIRST decides the fate of the pair. If that first pivot is z_i or z_j themselves, then z_i and z_j get compared (the pivot is compared against everyone, including its partner). If the first pivot is one of the middle elements, it splits z_i and z_j to opposite sides and they are never compared. Among the j - i + 1 elements in this block, each is equally likely to be the first one chosen as a pivot — that is exactly what 'uniformly at random' buys us. So the probability that z_i and z_j are ever compared is 2 / (j - i + 1): two favourable choices (z_i or z_j) out of j - i + 1 equally likely ones.
Define an indicator random variable X_{ij} that is 1 if z_i and z_j are ever compared and 0 otherwise. The total number of comparisons is the sum of X_{ij} over all pairs i < j. By linearity of expectation — the workhorse of the previous guides, which lets you add expectations even when the variables are tangled and dependent — the expected total is just the sum of the individual probabilities. The expectation of an indicator is exactly the probability it is 1, so E[X_{ij}] = 2 / (j - i + 1), and the whole running time analysis reduces to adding up these fractions.
Adding up to O(n log n)
Now we just sum E[X_{ij}] = 2 / (j - i + 1) over every pair i < j. Fix i and let j range upward: the denominators j - i + 1 run through 2, 3, 4, and so on, so the inner sum is 2 times (1/2 + 1/3 + 1/4 + ...), which is bounded by 2 times the harmonic sum 1 + 1/2 + 1/3 + ... + 1/n. That harmonic number is known to be about ln n, roughly the natural logarithm of n. Adding this up over all n choices of i gives an expected comparison count of at most 2 n times the harmonic number, which is O(n log n). One coin flip per pivot, one indicator per pair, one harmonic sum — and the fragile Theta(n^2) algorithm becomes a robust O(n log n) in expectation on every input.
E[comparisons] = sum over i<j of 2/(j-i+1)
<= sum over i of 2*(1 + 1/2 + ... + 1/n)
= 2n * H_n ~ 2n * ln n = O(n log n)Two honest footnotes. First, this is the expected number of comparisons, an average over the algorithm's own coin flips, NOT over a distribution of inputs — that distinction matters, because average-case analysis of plain quicksort assumes random inputs, whereas here the guarantee holds for the worst input you can devise. Second, the same indicator idea analyses randomized quickselect, which finds the k-th smallest element by recursing into only one side after each partition; there the fractions sum to a geometric series instead of a harmonic one and the expected cost drops to a clean O(n). The technique is the real prize here, not just the bound.
Hashing, and the adversary who breaks it
Now switch problems. A hash table stores items in an array of m slots, using a hash function h that maps each key to a slot number. To insert or look up a key you compute h(key) and go straight to that slot — O(1) if no two keys collide. A collision is when two distinct keys map to the same slot; we usually handle it by storing all colliding keys in a little list (a chain) at that slot. The whole performance story is the length of those chains: if every chain is short, operations are fast; if one chain holds most of the keys, a lookup degrades to scanning a long list and you lose the O(1) you came for.
Here is the catch that mirrors the quicksort pivot problem exactly. For ANY single fixed hash function h, there exist keys that all collide. The set of possible keys is far larger than the m slots, so by the pigeonhole principle some slot is the target of many keys; an adversary who knows your function can hand you exactly those keys and force every one into the same chain, dragging every operation to O(n). Publishing your hash function is like always picking the first element as a pivot: it hands the worst case to anyone who wants it. No fixed deterministic function can escape this, just as no fixed pivot rule can escape its bad input.
Universal hashing: random function, provable bound
The cure is universal hashing. Instead of one fixed function, you build a whole family H of hash functions and, at table-creation time, pick one function h from H uniformly at random. The family is called universal if, for every pair of distinct keys x and y, the probability (over the random choice of h) that they collide is at most 1/m — exactly the collision chance you would get if h scattered keys completely at random into m slots. The defining property is about pairs of keys, and that is all you need, because chain lengths are governed by how many other keys collide with the one you are looking up.
Watch the indicator trick reappear, because it is the same proof shape as quicksort. Suppose you are looking up key x in a table holding n keys. For each other key y, let an indicator variable be 1 if y collides with x. The expected length of x's chain is the sum of these indicators' expectations, and by linearity of expectation that is the sum, over the n-1 other keys, of the collision probabilities, each at most 1/m. So the expected chain length is at most (n-1)/m, which is below the load factor n/m. Keep m proportional to n and that expected length is a constant — expected O(1) per operation, on any set of keys, with the worst case now coming only from unlucky coin flips, never from a clever adversary.
A concrete family you can carry in your head: pick a prime p larger than any key, choose random a in {1, ..., p-1} and random b in {0, ..., p-1}, and let h(k) = ((a*k + b) mod p) mod m. Varying a and b sweeps out a universal family, and one can prove the 1/m collision bound holds for every pair of distinct keys. If you go one step further and pick m large enough — around n^2 slots — the expected number of collisions among all pairs drops below 1, so a few re-draws of the random function give you a table with NO collisions at all: that is perfect hashing, which builds a static dictionary with guaranteed worst-case O(1) lookups, all powered by the same idea of choosing the function at random.