Expected Running Time and Randomized Analysis

An algorithm's running time $T(n)$ is normally treated as a deterministic function of input size, or — after the ideas in Best, Average, and Worst Case Analysis — as a function that varies with the particular input of size $n$. Randomized analysis introduces a third source of variability: the algorithm itself flips coins, so even on a single, fixed input, running time is a random variable $T$ whose randomness comes entirely from those internal coin flips. The expected running time is $E[T]$, the average of $T$ weighted by the probability of each sequence of coin flips. This distinction is crucial and frequently blurred. Average-case analysis (studied for deterministic algorithms) assumes a probability distribution over inputs — e.g., "assume all $n!$ permutations are equally likely" — and is only meaningful if that assumption about the world actually holds. Randomized analysis makes no assumption about the input at all; the input can be chosen by a worst-case adversary who knows the algorithm's code. The randomness comes from the algorithm's own random number generator, which the adversary cannot predict in advance. The statement "randomized quicksort runs in $O(n\log n)$ expected time" is therefore a guarantee for every input array, not merely for a "typical" one. This makes randomized bounds strictly more robust than average-case bounds computed under an input distribution assumption, and it is why randomization is prized in adversarial settings such as network routing, hash table design in public-facing servers, and cryptographic protocols. The workhorse for computing $E[T]$ is the indicator random variable. For an event $A$ in a sample space, define

A one-line but load-bearing fact: $E[X_A] = \Pr[A]$, since $E[X_A] = 1\cdot \Pr[A] + 0 \cdot \Pr[\bar A] = \Pr[A]$. Many running-time quantities — total number of comparisons, total number of swaps, total probes in a hash table — can be written as a sum of indicator variables, one per elementary event (e.g., one per candidate pair of elements, one per attempted probe). Then linearity of expectation,

lets us compute the expectation of the sum by adding up the individual, easy-to-compute probabilities $\Pr[\text{event}_i]$ — crucially, even when the $X_i$ are statistically dependent on each other. This last point is what makes the technique so powerful: proving independence between events is often hard or false, but linearity of expectation needs no such proof.

The general recipe for bounding an expected running time has four steps. 1. Identify the elementary cost unit. Pick the dominant operation (comparisons for sorting, probes for hashing, edge relaxations for graph algorithms) so that total running time is proportional to the count of this unit, up to lower-order terms. 2. Express the total count as a sum of indicators. Enumerate a family of events $A_1, \dots, A_m$ (often "pair $(i,j)$ triggers the operation") and define $X_k = \mathbb{1}[A_k]$ so that the total count $X = \sum_k X_k$. 3. Compute $\Pr[A_k]$ for each event, usually via a clean combinatorial or probabilistic argument that does not require knowing anything about the other events. 4. Sum via linearity: $E[X] = \sum_k \Pr[A_k]$, then bound this sum (often by comparison to a harmonic series or a geometric series) to get a closed form such as $O(n \log n)$. We instantiate this recipe fully for randomized quicksort, the canonical example.

Randomized quicksort

Randomized quicksort chooses the pivot for each partition uniformly at random from the current subarray, independent of everything else. This single change converts quicksort's dreaded $\Theta(n^2)$ worst case (triggered by already-sorted input under a fixed pivot rule) into an $O(n\log n)$ expected case on every input. ``` RANDOMIZED-QUICKSORT(A, low, high): if low < high: p = RANDOM-INTEGER(low, high) # uniform pivot index swap A[p] and A[high] pivot = A[high] i = low - 1 for j = low to high - 1: if A[j] <= pivot: i = i + 1 swap A[i] and A[j] swap A[i+1] and A[high] q = i + 1 # final pivot position RANDOMIZED-QUICKSORT(A, low, q - 1) RANDOMIZED-QUICKSORT(A, q + 1, high) ``` Let the input, after relabeling, be the sorted sequence of ranks $z_1 < z_2 < \dots < z_n$ (any fixed array's elements can be relabeled by rank without changing the comparison structure). Define, for $i < j$:

The total number of comparisons performed by the algorithm is exactly

because quicksort compares any two elements at most once (once a pivot is chosen, it is compared against everything else in its subarray and never touched again).

Key probability computation. Consider $z_i, z_j$ with $i < j$, and the set $Z_{ij} = \{z_i, z_{i+1}, \dots, z_j\}$ of all elements between them (inclusive), of size $j - i + 1$. Two facts:

• $z_i$ and $z_j$ are compared if and only if one of them is chosen as a pivot before any other element of $Z_{ij}$ is chosen as a pivot. (If some element strictly between them is pivoted first, $z_i$ and $z_j$ end up in different subarrays and are never compared again.)
• Because pivots are chosen uniformly at random and independently at each recursive call, the relative order in which the elements of $Z_{ij}$ are first chosen as pivots (among calls that contain all of $Z_{ij}$) is a uniformly random permutation of $Z_{ij}$.

Hence

By linearity of expectation (no independence between the $X_{ij}$ needed):

Substitute $k = j - i$ (so $k$ ranges from $1$ to $n-1$, and for each $k$ there are $n-k$ valid pairs $(i,j)$):

using the harmonic number bound $H_n = O(\log n)$. This gives the clean, famous result:

Time complexity. The derivation above shows $E[\text{comparisons}] = O(n\log n)$ for randomized quicksort, on any input array — including already-sorted or adversarially constructed arrays. All other work (partitioning overhead, recursive call bookkeeping) is proportional to the number of comparisons plus $O(n)$ per level of recursion, so the total expected running time is $O(n\log n)$ as well. This should be contrasted with:

• Worst case (over both input and coin flips): still $\Theta(n^2)$, achieved if the random pivot happens to be the minimum or maximum element at every level — an event of vanishingly small but nonzero probability.
• Best case: $\Theta(n \log n)$, when pivots repeatedly split the array evenly.
• Expected case (this article's subject): $\Theta(n\log n)$ for every fixed input, because the $O(n^2)$ worst case has probability that decays exponentially in $n$ and contributes negligibly to the expectation.

Space complexity. Expected recursion depth is $O(\log n)$ (by a similar indicator/probabilistic argument on the size of subproblems shrinking geometrically in expectation), giving expected $O(\log n)$ auxiliary stack space; a bad sequence of pivots can still cause $O(n)$ depth, so implementations often recurse on the smaller partition first and iterate on the larger one to guarantee $O(\log n)$ worst-case space.

Correctness of the analysis (proof sketch). Two facts underpin the whole argument and deserve to be stated as an explicit invariant: 1. At most one comparison per pair. Quicksort's partitioning step compares every non-pivot element in a subarray to the pivot exactly once, and once an element is compared to a pivot it is placed in a side (left/right) that never merges with the other side again. Hence any two elements $z_i, z_j$ are compared at most once, across the whole execution. This is what licenses writing total comparisons as $\sum_{i<j} X_{ij}$ with no double-counting. 2. The "first pivoted wins" characterization is exact, not approximate. If neither $z_i$ nor $z_j$ is the first pivot chosen among $Z_{ij}$, some element strictly between them is pivoted first and permanently separates $z_i$ from $z_j$ into different recursive calls — they can never be compared afterward. Conversely if $z_i$ (or $z_j$) is the first of $Z_{ij}$ pivoted, it is compared directly against every other currently co-resident element of $Z_{ij}$, including $z_j$, during that partition step. This gives the iff characterization used above, and hence the exact probability $2/(j-i+1)$ (a uniformly random permutation places any one of $j-i+1$ elements first with equal probability $1/(j-i+1)$, and we want either of two designated elements to be first). 3. Linearity needs no independence. The events $X_{ij}$ are certainly not independent (e.g., knowing $z_1, z_2$ were compared changes the conditional structure of later comparisons), but $E[\sum X_{ij}] = \sum E[X_{ij}]$ holds regardless, because expectation of a sum is always the sum of expectations — this is a linear-algebra fact about the expectation operator, true unconditionally.

Honest tradeoffs. Randomized analysis gives an expectation guarantee, not a certainty: on any run there is a small probability of the $\Theta(n^2)$ pathological case. For applications demanding hard real-time guarantees, expectation bounds must be paired with concentration results (e.g., Chernoff-style tail bounds showing $\Pr[T > c\cdot n\log n]$ decays exponentially in $c$) or replaced by algorithms with deterministic worst-case bounds, such as introspective sort or heapsort, at some constant-factor cost in practice.

Take the (already sorted, hence adversarial for naive quicksort) input array of size $n = 5$:

Ranks equal values here, so $z_i = i$. We compute $\Pr[X_{ij}=1] = \frac{2}{j-i+1}$ for all $\binom{5}{2}=10$ pairs and sum.

Summing the right column: $1.0+0.667+0.5+0.4+1.0+0.667+0.5+1.0+0.667+1.0 = 8.4$ (approximately), so

for this $n=5$ sorted array — versus the worst-case $\binom{5}{2}=10$ comparisons a fixed always-pick-first-element quicksort would need on this same input (achieving its full $\Theta(n^2)$ regime), and versus the theoretical best case around $n\log_2 n \approx 11.6$ comparisons for merge-sort-style optimal splitting scaled to this small n (small-$n$ constants make direct comparison approximate, but the qualitative point holds: randomization has converted a worst-case input into a moderate expected cost). To see the mechanism concretely, trace one possible random execution. Suppose the random pivot choices are: first call picks pivot index $3$ (value $3$), splitting into $[1,2]$ and $[4,5]$; then $[1,2]$ picks pivot $1$ (value $1$, so no further split needed on that side after one comparison), and $[4,5]$ picks pivot $2$ (value $4$ relative to that subarray). Tallying comparisons in this run: partitioning around $3$ costs $4$ comparisons (comparing $1,2,4,5$ against pivot $3$); partitioning $[1,2]$ around $1$ costs $1$ comparison; partitioning $[4,5]$ around $4$ costs $1$ comparison. Total for this particular run: $6$ comparisons — below the expectation of $8.4$, illustrating that expectation is an average over many possible coin-flip sequences, some cheaper, some (like always picking the min/max) far more expensive.

:::warning[The single most dangerous mix-up is treating an expected-time bound as if it were a worst-case bound.] An engineer who reads "randomized quicksort is $O(n\log n)$" and assumes this holds on every execution, not merely on average, will be unprepared for the rare but real $\Theta(n^2)$ run — a serious problem in latency-sensitive or adversarial settings (e.g., an attacker who can observe outputs and retry). Always state explicitly whether a bound is expected, worst-case, or high-probability (i.e., holds with probability $1 - n^{-c}$), since these are three different, non-interchangeable guarantees.

Randomized analysis, indicator random variables, and their combination for algorithm running times matured through the intersection of probability theory and computer science in the mid-to-late 20th century. Tony Hoare invented quicksort itself in 1959–1961; the randomized-pivot analysis and its rigorous expected-time treatment came later as randomized algorithms crystallized into their own subfield, driven by figures who formalized "algorithms that flip coins" as a first-class object of study alongside deterministic ones.

Expected running time analysis is not a theoretical nicety — it underlies working infrastructure. Standard library sort routines (introspective sort implementations in C++ and elsewhere) use randomized or pseudo-randomized pivot selection to defeat adversarial or pathological inputs while retaining the $O(n\log n)$ expected performance derived above. Hash table implementations in language runtimes and databases randomize their hash functions (universal hashing) specifically so that expected bucket-chain lengths stay $O(1)$ regardless of what keys an adversary supplies — an application of the exact indicator-variable technique used here, just with "collision events" replacing "comparison events." Randomized min-cut (Karger's algorithm), randomized primality testing (Miller–Rabin, used in cryptographic key generation), skip lists (used in Redis and LevelDB as a simpler alternative to balanced trees), and randomized load balancing in distributed systems all rely on the same expectation-over-coin-flips paradigm. This analytic toolkit is also the direct stepping stone toward understanding Comparison-Based Sorting Lower Bounds, where the expected number of comparisons any correct sorting algorithm must perform is bounded below using an information-theoretic (entropy) argument dual to the indicator-variable upper-bound technique developed here — expectation appears on both sides of the sorting complexity story, as an achievable upper bound and as an unavoidable lower bound.

Ask the tutor: How would the indicator-variable argument change if we analyzed randomized quickselect instead of full quicksort?