Introduction to Randomized Algorithms

A randomized algorithm is an algorithm that, in addition to its input, has access to a source of random bits and uses them to make some of its decisions. Formally, we augment the algorithm with an internal random variable (or sequence of coin flips) $R$, and the algorithm's output and running time become random variables that depend on both the input $x$ and $R$. Crucially, the distribution over $R$ is chosen by the algorithm designer (uniform bits, uniform random pivot, uniform random hash function, etc.) and is completely independent of the input — this independence is what defeats an adversary who can see the algorithm's code but not its coin flips. There are two canonical species, distinguished by which aspect of behavior is randomized:

• A Las Vegas algorithm always produces a correct answer. What varies from run to run is the running time, which is a random variable. We analyze it via its expected running time, $\mathbb{E}[T(x)]$, taken over the internal randomness, for a worst-case input $x$. Randomized quicksort is the flagship example: it always sorts correctly, but the number of comparisons it performs is random.
• A Monte Carlo algorithm runs in a fixed (typically worst-case deterministic) time bound, but it may return an incorrect answer with some bounded probability $\varepsilon$. We analyze it via its error probability, and we typically show that repeating the algorithm independently and taking a majority vote (or similar aggregation) drives $\varepsilon$ down exponentially fast — a process called error amplification or probability amplification. The Rabin–Karp string-matching algorithm, in its randomized hash-comparison mode, is a Monte Carlo algorithm: a rolling hash match is treated as a full match without verification, risking a false positive with tiny probability.

The key technical tool for analyzing both flavors is linearity of expectation: for any random variables $X_1,\dots,X_n$ (independent or not),

This identity holds unconditionally — no independence assumption is needed — which makes it the single most useful fact in randomized algorithm analysis. Combined with indicator random variables ($X_i = 1$ if some event happens, $0$ otherwise, so $\mathbb{E}[X_i] = \Pr[\text{event}]$), it lets us compute the expected value of a complicated quantity (like "total number of comparisons") by decomposing it into simple pairwise events whose probabilities we can compute directly, even when those events are far from independent of each other.

We build the machinery in three layers: (1) the general recipe for expected-time analysis via indicator variables, (2) the randomized quicksort algorithm itself, and (3) the indicator-variable argument that pins down its expected comparison count exactly.

Layer 1 — the indicator-variable recipe. Suppose we want $\mathbb{E}[T]$ where $T$ counts some total quantity (comparisons, probes, collisions) built from many small "did-this-pairwise-event-happen" contributions. The recipe is always the same three steps: 1. Write $T = \sum_{i} X_i$, where each $X_i \in \{0,1\}$ is an indicator for a well-chosen elementary event. 2. Compute $\mathbb{E}[X_i] = \Pr[\text{event } i]$ for each $i$ — usually an easy, local probability computation. 3. Apply linearity: $\mathbb{E}[T] = \sum_i \Pr[\text{event } i]$, and bound or evaluate the sum. The power of this recipe is that step 3 needs no independence between the $X_i$. This matters enormously in quicksort, where whether elements $a$ and $b$ are compared is not independent of whether $b$ and $c$ are compared — yet linearity does not care.

Layer 2 — randomized quicksort. The algorithm is standard quicksort with one change: the pivot at every recursive call is chosen uniformly at random from the current subarray, instead of, say, always the first or last element. ``` RANDOMIZED-QUICKSORT(A, lo, hi): if lo < hi: p = RANDOMIZED-PARTITION(A, lo, hi) RANDOMIZED-QUICKSORT(A, lo, p - 1) RANDOMIZED-QUICKSORT(A, p + 1, hi) RANDOMIZED-PARTITION(A, lo, hi): i = RANDOM-INTEGER(lo, hi) // uniform over {lo, ..., hi} swap A[i] and A[hi] // move random pivot to the end return PARTITION(A, lo, hi) // standard Lomuto/Hoare partition using A[hi] as pivot PARTITION(A, lo, hi): // Lomuto scheme, pivot = A[hi] pivot = A[hi] j = lo - 1 for k = lo to hi - 1: if A[k] <= pivot: j = j + 1 swap A[j] and A[k] swap A[j + 1] and A[hi] return j + 1 ``` The only change from deterministic quicksort is the single call to `RANDOM-INTEGER`, which costs $O(1)$ and is assumed to return a uniformly random integer in the given range, independent of all past random choices. Everything else — the partition logic, the recursive structure, the base case `lo < hi` (an empty or singleton subarray is already sorted) — is untouched. Correctness is inherited directly from deterministic quicksort's correctness (the partition invariant places every element on the correct side of the pivot), because randomness only affects which element is chosen as pivot, never the logic that decides how partitioning proceeds. This is precisely what makes it a Las Vegas algorithm: correctness is unconditional, and only the running time is a random variable.

Layer 3 — the indicator-variable argument. Let $A$ be an array containing the input elements, and — since only the relative order matters to a comparison-based algorithm — let $z_1 < z_2 < \cdots < z_n$ denote the elements in sorted rank order (we do not need to know the original array order, only that all elements are distinct for this cleanest version of the proof; ties are handled by treating comparisons consistently, e.g., breaking ties by original position). Define the indicator

The total number of comparisons performed by the algorithm is

because in Lomuto partitioning, any two elements are compared at most once in the entire algorithm — once one of them becomes a pivot, it is compared to everything remaining in its subarray exactly once, and it is never involved in a comparison again after partitioning finishes. By linearity of expectation,

Now the key combinatorial fact: consider the set $Z_{ij} = \{z_i, z_i+1, \dots, z_j\}$ of elements with rank between $i$ and $j$ inclusive (there are $j - i + 1$ of them). $z_i$ and $z_j$ are compared if and only if the first pivot ever chosen from $Z_{ij}$ is either $z_i$ or $z_j$ itself. Why: as long as pivots chosen so far are strictly between $z_i$ and $z_j$ in rank, $z_i$ and $z_j$ stay together in the same recursive subarray (a pivot splits its subarray, and any pivot with rank strictly between $i$ and $j$ separates $z_i$ from $z_j$ into different sides without ever comparing them, since Lomuto only compares the pivot to others, not `z_i` to `z_j` directly). The moment the first pivot from $Z_{ij}$ is chosen, either it is $z_i$ or $z_j$ (in which case they get compared, since the pivot is compared against every other element remaining in its subarray including the other one), or it is some element strictly between them (in which case $z_i$ and $z_j$ are permanently separated into different recursive calls and can never be compared again). Since the pivot is chosen uniformly at random among the current subarray, and every element of $Z_{ij}$ is equally likely to be the first one chosen from that set (a standard fact: given a uniformly random sequence of distinct picks, each element of a fixed subset is equally likely to appear first among that subset),

Substituting and simplifying with $k = j - i$:

where $H_n = \sum_{k=1}^n 1/k \approx \ln n$ is the $n$-th harmonic number.

Time complexity. We derived $\mathbb{E}[T] = O(n\log n)$ comparisons above, and since every other operation (swaps, recursive calls, array bookkeeping) is a constant multiple of the comparison count plus $O(n)$ overhead for partitioning at each level, the total expected running time is

for every input array, deterministic or adversarially constructed — the bound has no dependence on the input's initial order because the only randomness is in pivot choice, and the analysis never assumed anything about the input distribution. This is the crucial contrast with deterministic quicksort: a fixed pivot rule has some worst-case input (e.g., a sorted array, if you always pick the last element) forcing $\Theta(n^2)$ time. Randomized quicksort has no such fixed bad input, because the bad event ("always pick an extreme pivot") now depends on random coin flips rather than input structure, and that event has probability that decays doubly-exponentially in the recursion depth. The worst case is still $\Theta(n^2)$: with tiny but nonzero probability the random pivot choices could be unlucky at every level (always picking the minimum or maximum element), reproducing the fully unbalanced recursion tree. But — and this is the point of Las Vegas analysis — the probability of taking, say, more than $c \cdot n \log n$ time decays exponentially in $c$ (a fact provable via a Chernoff-style tail bound on recursion depth), so in practice and in expectation the algorithm is reliably fast.

Space complexity. In-place partitioning uses $O(1)$ auxiliary space per call; the recursion stack depth is $O(\log n)$ in expectation (and $O(n)$ in the worst case, though this can be forced down to guaranteed $O(\log n)$ worst-case stack space by always recursing first into the smaller partition and using a loop or tail-call optimization for the larger one).

Correctness argument. Correctness of randomized quicksort follows immediately from the correctness of the underlying deterministic partitioning routine, by an invariant induction on subarray size completely unaffected by which pivot value happened to be chosen:

• Base case: a subarray of size $0$ or $1$ (`lo >= hi`) is trivially sorted; no recursive call is made.
• Inductive step: `PARTITION` maintains the loop invariant that after processing index $k$, all elements in $A[lo..j]$ are $\le$ pivot and all elements in $A[j+1..k]$ are $>$ pivot — this invariant holds regardless of which element was swapped into the pivot position, since the partition procedure only inspects values, never how the pivot was selected. After partitioning, the pivot sits at its final sorted position (index $p$), with everything smaller to its left and everything larger to its right. By the induction hypothesis, the two recursive calls correctly sort $A[lo..p-1]$ and $A[p+1..hi]$, so the whole array is sorted.

Since randomness enters only in the choice of pivot index, and the induction argument never used any property of that choice beyond "some valid index in range," the algorithm is correct with probability 1, on every input — the defining feature of a Las Vegas algorithm. Compare this with a Monte Carlo algorithm's correctness argument, which instead bounds $\Pr[\text{output is wrong}]$ and typically appeals to a union bound or a tail inequality over the random choices (e.g., in randomized pattern matching, bounding the chance of a spurious hash collision).

Honest tradeoffs. Randomized quicksort trades a worst-case time guarantee for an unconditional expected-time guarantee that is immune to adversarial inputs — but it does not eliminate the worst case, merely makes it astronomically unlikely and input-independent. It also requires a genuine source of randomness; a predictable or attacker-known pseudorandom generator reintroduces the adversarial vulnerability it was designed to remove. Compared to deterministic linear-time median-of-medians pivot selection (which guarantees $O(n\log n)$ worst-case time), randomized quicksort is simpler and faster in practice due to lower constant factors, at the cost of only a probabilistic guarantee.

Trace randomized quicksort on the array $A = [5, 3, 8, 1, 9, 2]$ (all distinct, ranks $1,\dots,6$ corresponding to sorted values $1,2,3,5,8,9$), suppose the random pivot choices (as array indices, 0-indexed) happen to be as follows.

Reconstructing: call 1 compares pivot $9$ against each of $5,3,8,1,2$ — five comparisons — and correctly places $9$ at the far right since it is the maximum. Call 2 compares pivot $3$ against $5,8,1,2$ (four comparisons), splitting into $\{1,2\}$ and $\{8,5\}$. Call 3 compares $2$ against $1$ (one comparison). Call 4 compares $5$ against $8$ (one comparison). Total comparisons: $5+4+1+1 = 11$. Check against the indicator-variable formula: for $n=6$, $\mathbb{E}[T] < 2(n-1)H_n = 2(5)(1+\tfrac12+\tfrac13+\tfrac14+\tfrac15+\tfrac16) \approx 10 \times 2.45 = 24.5$ — an upper bound, and our traced run (11 comparisons) is comfortably below it, since this particular sequence of pivots happened to be quite well-balanced (the very first pivot, $9$, was the maximum, which is actually a bad split — but the very next pivot, $3$, recovered nicely by splitting $\{1,2\}$ from $\{8,5\}$ almost evenly). This illustrates the core phenomenon: individual unlucky pivots (like picking the maximum first) do not doom the algorithm, because subsequent independent random choices tend to average out to balanced splits, which is exactly what the expectation calculation captures in aggregate rather than assuming every level is balanced. For contrast, consider what deterministic "always pivot on last element" quicksort does on the already-sorted array $[1,2,3,5,8,9]$: pivot $9$ (max) → split $[1,2,3,5,8]$ vs $[\,]$; pivot $8$ (max again) → split $[1,2,3,5]$ vs $[\,]$; and so on — a fully degenerate chain making $\binom{6}{2}=15$ comparisons for $n=6$, and $\Theta(n^2)$ in general, with no randomness required to force this — any sorted input triggers it deterministically. Randomized quicksort on this exact same sorted input has identical expected performance to any other input, because pivot selection ignores array content entirely.

The theory of randomized algorithms crystallized as a distinct field in the 1970s, driven by primality testing and combinatorial algorithm design, though the underlying probabilistic reasoning traces back to earlier work in statistics and information theory.

Randomized quicksort and its relatives are the default sorting routines inside most production language runtimes and standard libraries, precisely because randomizing (or using a well-mixed pivot heuristic) defeats crafted worst-case inputs that plagued early deterministic implementations — this was the direct motivation behind switching several standard-library sort implementations to randomized or introspective (hybrid) variants after complexity-attack vulnerabilities were publicly demonstrated. Randomized load balancing (the "power of two random choices") underlies request routing in distributed web services and data-center job scheduling, achieving near-optimal balance with far less coordination overhead than deterministic round-robin schemes. Monte Carlo algorithms in the Rabin–Karp family power plagiarism detectors, DNA sequence alignment tools, and version-control diffing, all of which need fast substring/pattern matching over enormous texts where an occasional (exponentially rare) false positive is an acceptable price for massive speedups. Cryptographic key generation depends on randomized primality testing (Miller–Rabin), since deterministic alternatives, while they exist (AKS), remain far slower in practice. Randomized sketching and sampling techniques — closely related in spirit to the indicator-variable analysis developed here — underlie streaming analytics systems that estimate statistics (distinct counts, frequent items, quantiles) over data streams too large to store in memory, a topic that connects directly forward to hashing-based data structures, including the universal hash families explored in Introduction to Hashing, and backward to the same rolling-hash ideas from Rabin-Karp and Rolling Hashes and the systematic pruning ideas from Branch and Bound that also try to avoid worst-case blowups, albeit deterministically.

Ask the tutor: How would the indicator-variable argument change if the input array contains duplicate elements?