6. Randomization: Matrix Multiply, Quicksort

What this lecture covers

The lecture answers what it means for an algorithm to use randomness to make decisions, and how to analyze the resulting probabilistic guarantees on correctness and runtime. It introduces the distinction between Monte Carlo algorithms (probably correct, deterministically fast) and Las Vegas algorithms (always correct, probably fast), then works through two concrete examples: Freivalds' algorithm for verifying matrix multiplication, and several variants of quicksort.

This is the sixth lecture in MIT's Design and Analysis of Algorithms course, opening a new module on randomized algorithms. After watching, you should be able to state the difference between Monte Carlo and Las Vegas algorithms, explain how Freivalds' algorithm verifies A * B = C in O(n^2) time with bounded error probability, and describe why randomizing the pivot choice (or retrying until a balanced partition is found) gives quicksort expected O(n log n) running time.

Key ideas

• Randomized algorithm: an algorithm that generates random values during execution and makes decisions based on them, so that different runs on the same input can take different amounts of time or produce different outputs.
• Monte Carlo algorithms: probably correct — they run in a fixed time bound but may return an incorrect answer with some bounded probability, which can be driven down by running independent repetitions.
• Las Vegas algorithms: probably fast — they always return the correct answer but their running time is a random variable, so the goal is to bound the expected running time.
• Freivalds' algorithm: checks whether C = A * B for n x n matrices in O(n^2) time by picking a random binary vector r and testing whether A(Br) = Cr, instead of recomputing the full O(n^3) product.
• No false negatives: if AB = C, then A(Br) = Cr always holds by associativity, so Freivalds' algorithm never rejects a correct product.
• Bounded false positives: if AB != C, the probability that a randomly chosen r fails to detect the error is at most one half, proved with a counting argument that pairs each "bad" r (where Dr = 0) with a "good" one (Dr' != 0) via a one-to-one mapping.
• Basic quicksort: pivoting on a fixed position (such as the first element) gives Theta(n^2) worst-case time, but on randomly shuffled input performs well in practice.
• Median-based quicksort: using deterministic linear-time median finding as the pivot guarantees Theta(n log n) worst-case time, but the constant factors make it impractical compared to basic quicksort.
• Paranoid (Las Vegas) quicksort: repeatedly picks a random pivot and retries the partition until both sides have at most 3n/4 elements, giving O(n log n) expected time with a simple recurrence-tree argument.

Walkthrough

Randomized algorithms, Monte Carlo and Las Vegas (0:00)

The lecture defines a randomized algorithm as one that generates random numbers and bases decisions on them, so repeated runs on the same input can differ in running time or output. It introduces Monte Carlo algorithms (probably correct, deterministically or reliably fast) and Las Vegas algorithms (always correct, probably fast), with primality testing mentioned as an example that can behave like a Monte Carlo algorithm.

Setting up Freivalds' algorithm (11:11)

The problem is verifying whether a claimed product C = A * B for n x n matrices is correct, without redoing the O(n^3) multiplication. Freivalds' algorithm picks a random binary vector r (each entry independently 1 with probability one half) and checks whether A(Br) = Cr, which requires three matrix-vector products, each O(n^2), for a total of O(n^2) per trial. Running k independent trials drives the false-positive probability down to 1/2^k while keeping the total cost O(kn^2).

Why there are no false negatives (27:23)

If AB = C, then A(Br) = (AB)r = Cr by associativity of matrix multiplication, so the algorithm always outputs "yes" when the product is actually correct.

Bounding the false-positive probability (29:26)

Defining the difference matrix D = AB - C, the claim to prove is that if D != 0, then a random r satisfies Dr != 0 with probability at least one half. The proof picks a nonzero entry D[i][j], constructs a one-hot vector v with a 1 in position j, and shows that for any "bad" r with Dr = 0, flipping the j-th bit of r (computing r' = r + v in mod-2 arithmetic) produces a "good" r' with Dr' != 0. Because this r <-> r' mapping is one-to-one, at least half of all possible r vectors are good, giving the claimed bound.

Basic quicksort and its worst case (49:51)

Quicksort is introduced as an in-place, divide-and-conquer sort where the work happens in the divide (partition) step rather than the merge step. Basic quicksort, which always pivots on a fixed element such as A[1], has Theta(n^2) worst-case time on sorted or reverse-sorted input, since the recurrence T(n) = T(n-1) + Theta(n) solves to quadratic time. In practice, shuffling the input first makes basic quicksort perform well, with expected Theta(n log n) time.

Guaranteeing worst-case time with median pivots (1:02:09)

Using the linear-time deterministic median-finding algorithm to select the pivot at every level guarantees perfectly balanced partitions, giving the recurrence T(n) = 2T(n/2) + Theta(n), which solves to Theta(n log n) worst-case time. The lecture notes this is impractical because the median-finding overhead makes it slower than basic quicksort in practice, illustrating the gap between asymptotic complexity and real performance.

Paranoid quicksort and its expected-time analysis (1:10:14)

Paranoid quicksort picks a random pivot, partitions, and retries until both resulting subarrays have size at most 3n/4 (a "good" pivot, which occurs with probability at least one half). This gives the recurrence T(n) = T(n/4) + T(3n/4) + 2cn, where the factor of 2 accounts for the expected number of retries. Drawing the (unbalanced) recursion tree shows that each level sums to 2cn of total work and the tree has at most log_{4/3}(n) levels, giving O(n log n) expected time.

Before you watch

• Review the earlier lecture on deterministic linear-time median finding (the five-way partition, median-of-medians algorithm), since it is reused here as an intelligent quicksort pivot strategy.
• Be comfortable with recurrence relations and recursion trees, since both Freivalds' probability bound and the paranoid quicksort analysis rely on careful counting arguments rather than the master method.

Check your understanding

1. Why does Freivalds' algorithm never produce a false negative, but can produce a false positive?
2. How does the one-to-one mapping between "bad" and "good" random vectors r establish that at least half of all r vectors detect an incorrect matrix product?
3. Why does basic quicksort run in Theta(n^2) worst-case time, and why does shuffling the input first fix this in practice?
4. Why is median-based quicksort worse in practice than basic quicksort, despite having a better worst-case asymptotic bound?
5. In paranoid quicksort, why does the recurrence T(n) = T(n/4) + T(3n/4) + 2cn still solve to O(n log n) even though the partitions are unbalanced?