Algorithms
Randomized Algorithms
Difficulty: Advanced
Plain quick sort with a fixed pivot is O(n log n) on random input but O(n^2) on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes O(n log n)...
Randomized Algorithms
Plain quick sort with a fixed pivot is O(n log n) on random input but O(n^2) on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes O(n log n) expected on every input, because the adversary no longer knows where the algorithm will partition. Randomization is not a hack here; it is a principled way to break the dependency between input and runtime.
Randomized Algorithms trains that style of thinking. You will distinguish Las Vegas algorithms (always correct, randomized running time) from Monte Carlo algorithms (bounded running time, possibly wrong) and reason about expected-value guarantees. You will analyze Randomized Quick Sort to see why expected O(n log n) is robust against adversarial input, implement Quick Select for O(n) expected-time kth-element selection plus the deterministic median-of-medians variant, and walk through Reservoir Sampling Algorithm R for uniformly sampling k elements from a stream of unknown length, including the proof of uniformity. The lesson also revisits skip lists and treaps from the data-structures track as randomized alternatives to balanced BSTs.
In Sorting (Elementary), you saw worst-case-sensitive sorting. Recursion Fundamentals gave you the call-stack model behind quick sort and quick select. This lesson injects controlled randomness into those frameworks.
Next, Approximation Algorithms trades exactness for polynomial time on NP-hard inputs.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Distinguish between Las Vegas and Monte Carlo randomized algorithms.
Implement Randomized QuickSort and explain why random pivot selection avoids worst-case O(n^2) behavior.
Implement QuickSelect to find the kth smallest element in expected O(n) time.
Implement Reservoir Sampling (Algorithm R) and prove that each element has equal probability of being selected.
Analyze the expected time complexity of randomized algorithms.
Why This Matters
01
Randomized QuickSort achieves O(n log n) expected time on any input by eliminating adversarial worst cases -- it is the default sort in many standard libraries.
02
QuickSelect finds the kth smallest element in expected O(n) time, making it the go-to algorithm for median finding, top-K problems, and order statistics.
03
Reservoir Sampling solves the fundamental streaming problem of sampling uniformly from data of unknown or infinite length using only O(k) memory.
04
Understanding randomized algorithms teaches you to reason about expected behavior and probabilistic guarantees -- essential skills for system design and algorithm analysis.
Key Terms
6 terms you'll encounter in this lesson
Las Vegas Algorithm
A randomized algorithm that always produces the correct result but has a random running time. Example: Randomized QuickSort always sorts correctly; the running time varies but is O(n log n) expected.
Monte Carlo Algorithm
A randomized algorithm that runs in bounded time but may produce an incorrect result with some probability. Example: Miller-Rabin primality test runs in polynomial time but has a small probability of error.
QuickSelect
An algorithm that finds the kth smallest element by partitioning around a random pivot and recursing into only one side. Expected time: O(n). Also known as Randomized Selection.
Reservoir Sampling
An algorithm for choosing k items uniformly at random from a stream of unknown length n. Each item has exactly k/n probability of being in the final sample. Uses O(k) space.
Randomized Pivot
Choosing the partition pivot uniformly at random instead of using a fixed position (like first or last element). This ensures O(n log n) expected time regardless of input ordering.
Expected Time Complexity
The average running time over all possible random choices made by the algorithm (not over all possible inputs). For Randomized QuickSort, this is O(n log n) on every input.
Heads Up
Common misconceptions to watch out for
"Randomized QuickSort has O(n^2) average case"
With random pivot selection, Randomized QuickSort has O(n log n) expected time on EVERY input. The O(n^2) worst case exists but occurs with negligibly small probability (roughly 1/n!).
"QuickSelect is just QuickSort that stops early"
QuickSelect only recurses into ONE side of the partition (the side containing the target index), not both. This makes it O(n) expected instead of O(n log n). The geometric series 1 + 1/2 + 1/4 + ... = 2 explains the linear bound.
"Reservoir Sampling favors elements seen later in the stream"
Reservoir Sampling gives every element exactly the same probability (k/n) of being in the final sample. Later elements have a higher chance of entering the reservoir, but they also face more rounds of potential replacement.