R4. Randomized Select and Randomized Quicksort

What this lecture covers

This recitation works through the expected-time analysis of two randomized algorithms introduced in the preceding lecture: randomized select (finding the i-th smallest element, called "quick find" here) and randomized quicksort. Rather than relying on the master method, which does not apply to recurrences involving an expectation over a random pivot rank, the TA demonstrates a guess-and-verify induction technique: propose a bound, substitute it into the recurrence, and check whether the induction step holds.

It follows the lecture on randomization (Monte Carlo and Las Vegas algorithms) and pairs with the deterministic median-finding algorithm from earlier in the course. After watching, you should be able to set up the expectation recurrence for a randomized divide-and-conquer algorithm and carry out an inductive proof that guesses a bound, substitutes it, and refines the guess until the induction succeeds.

Key ideas

• Randomized select ("quick find"): picks a random pivot x, partitions the array around it, and recurses into only the side containing the target rank i, with recurrence T(n) <= max(T(K-1), T(n-K)) + Theta(n) where K is the random pivot's rank.
• Expectation over the recursion: because K is random, the algorithm's exact running time cannot be pinned down, so the analysis instead bounds E[T(n)] by averaging over all possible values of K, each with probability 1/n.
• Guess-and-verify induction: since these recurrences do not fit the master method, the technique is to hypothesize a bound (such as E[T(n)] <= Bn), substitute the inductive hypothesis for smaller subproblems, and check whether the resulting inequality holds; if it fails, try a larger bound.
• Sum approximation by integrals: sums like sum(j) or sum(j^2) over a range are approximated by integrals to get their leading-order behavior (Theta(n^2) and Theta(n^3) respectively) when computing the substituted recurrence.
• Randomized select is Theta(n) expected: the guess E[T(n)] = Theta(n) succeeds for quick find because only one subproblem is recursed into, so the summed work has a 3/8 n^2 leading term that is dominated by the linear guess.
• Randomized quicksort is Theta(n log n) expected: for quicksort, both subarrays are recursively sorted (a sum instead of a max in the recurrence), so the guesses Theta(n) and Theta(n^2) both fail the induction step, and only Theta(n log n) succeeds.
• Average vs. expected vs. amortized time: "average" running time averages over possible inputs (a weak guarantee, since it assumes something about input distribution); "expected" running time averages over the algorithm's own internal randomness, independent of the input; "amortized" running time averages over a sequence of operations.

Walkthrough

Correction to problem set 2 on combining B-trees (0:00)

The recitation opens with a correction to a homework problem about merging two B-trees of different heights, noting that simply making the new key a root with two children can produce an invalid node if it doesn't meet the minimum-children requirement; the fix is to insert the key into the last child of the taller tree and let splits cascade if needed.

Recap of randomized select and its recurrence (2:52)

The recitation contrasts the deterministic median-of-medians algorithm (using groups of five, which is fast in the worst case but complex) with randomized select: pick a random element, partition around it, and recurse into whichever side contains the target rank i. Because the pivot's rank K is random, the recurrence T(n) <= max(T(K-1), T(n-K)) + Theta(n) cannot be solved directly, so the analysis takes an expectation over all choices of K.

Proving randomized select is Theta(n) by induction (9:09)

Guessing E[T(n)] <= Bn, the recitation substitutes this into the expectation sum, approximates the resulting sum of j terms as roughly 3/8 n^2 using the observation that summing from n/2 to n is about 1/2 n^2 - 1/8 n^2, and shows the induction step holds for a suitable constant B, confirming E[T(n)] = Theta(n).

Randomized quicksort's recurrence (21:40)

Quicksort differs from select only in that both partitions must be recursively sorted, turning the max in the recurrence into a sum: E[T(n)] = (1/n) * sum_{J=1}^{n} (T(J-1) + T(n-J)) + Theta(n). The recitation shows that the earlier guess of Theta(n) fails this induction step, since the sum's range now spans the whole array rather than just the upper half.

Trying larger bounds for quicksort (25:44)

The recitation successively tries Theta(n^2) (too weak a claim — proves an upper bound but not a tight one), n^(1+epsilon) for any epsilon > 0 (also holds, using the integral approximation for sum(j^(1+epsilon))), and finally Theta(n log n), computing sum(j log j) by integral approximation as roughly (1/2) n^2 log n minus lower-order terms. This bound satisfies the induction step, establishing E[T(n)] = O(n log n) for randomized quicksort.

Average, expected and amortized time (38:00)

The recitation closes by distinguishing three notions of "average" running time. Average running time averages over possible inputs and is a weak guarantee, since a non-randomized algorithm (always picking the first element as pivot) can behave well on random input but badly on adversarial input like a sorted array. Expected running time averages over the algorithm's own randomness and gives guarantees independent of the input, at the cost of needing a good source of randomness. Amortized running time averages over a sequence of operations on the same data structure.

Before you watch

• Watch the main randomization lecture on Monte Carlo and Las Vegas algorithms, including randomized quicksort, since this recitation assumes that setup.
• Review the deterministic linear-time median-finding (median-of-medians) algorithm from earlier in the course, which is used here as a point of comparison.
• Be comfortable with basic summation formulas and approximating sums by integrals, since the inductive proofs rely on this technique throughout.

Check your understanding

1. Why can't the master method be applied directly to the recurrence for E[T(n)] in randomized select?
2. Why does the guess E[T(n)] = Theta(n) succeed for randomized select but fail for randomized quicksort?
3. How does approximating sum(j) by an integral help establish that randomized select runs in expected Theta(n) time?
4. What is the difference between "average" running time and "expected" running time, and why is the expected-time guarantee for randomized quicksort stronger?