A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A randomized algorithm uses random coin flips as part of its logic, making its behavior (runtime, output, or both) a random variable rather than a deterministic quantity. Randomization often yields simpler, faster, or more elegant algorithms than the best known deterministic alternatives. Randomized quicksort achieves O(n log n) expected time with no adversarial worst case; randomized min-cut (Karger's algorithm) finds minimum cuts with high probability through simple edge contractions. The analysis of randomized algorithms relies on probability tools — linearity of expectation, tail bounds, and the probabilistic method — to provide rigorous guarantees despite the inherent unpredictability.
You already understand deterministic algorithm analysis — given an input, the algorithm follows a fixed sequence of steps and you analyze the worst case. Randomized algorithms break this model by introducing coin flips into the algorithm's logic. The algorithm's behavior on a fixed input becomes a random variable, and the analysis shifts from worst-case determinism to probabilistic guarantees. This is not the same as average-case analysis over random inputs: the randomness is internal to the algorithm, and the guarantees hold for every input.
The power of randomization is surprising. Randomized quicksort achieves O(n log n) expected time on every input — no adversary can force quadratic behavior because the adversary cannot predict the random pivot choices. The analysis uses linearity of expectation: define indicator random variables X_ij for whether elements i and j are compared, compute Pr[X_ij = 1] = 2/(j-i+1) from the observation that i and j are compared exactly when one of them is the first pivot chosen from the range between them, then sum over all pairs to get the harmonic series. No independence assumptions are needed because linearity of expectation holds unconditionally.
Karger's min-cut algorithm illustrates a different flavor of randomization. The algorithm repeatedly contracts a uniformly random edge until only two vertices remain, and the edges between them form a candidate cut. A single run finds a specific minimum cut with probability at least 2/n(n-1), which seems terrible — but repeating O(n2 log n) times and keeping the best cut drives the failure probability to inverse polynomial. This technique of probability amplification through independent repetition is a recurring theme: weak probabilistic guarantees become strong ones through repetition, as long as verification is cheap.
The theoretical foundation for analyzing randomized algorithms draws on tools you know from probability — linearity of expectation, Markov's and Chebyshev's inequalities, Chernoff bounds — and applies them in algorithmic contexts. Tail bounds are particularly important: they tell you not just the expected behavior but how tightly concentrated the actual behavior is around the expectation. An algorithm with O(n log n) expected time is less useful if the variance is huge, but Chernoff bounds often show that the running time is sharply concentrated, deviating from the expectation with only exponentially small probability. This combination of simplicity, efficiency, and provable concentration makes randomized algorithms indispensable in modern algorithm design.