Average-Case Analysis

Worst-case analysis is the pessimist's tool: it names the single most hostile input and reports how badly the algorithm does on it. That is exactly what you want for a flight controller or a cryptographic primitive. But it can be wildly misleading for everyday code. Quicksort's worst case is \Theta(n^2), yet it is the sort the standard libraries reach for — because on a typical input it flies. To capture "typical" we stop looking at one adversarial input and instead average over all inputs, weighted by how likely each is.

Average-case analysis treats the running time as a random variable — a function of a randomly drawn input — and computes its expectation. The whole subject rests on two astonishingly powerful, almost embarrassingly simple tools: linearity of expectation and indicator random variables. Master those two and a surprising number of "hard" counting problems collapse into a couple of lines of arithmetic.

Running time as an expectation

Fix an input distribution — a probability for each possible input of size n. (The most common assumption is the uniform one: every ordering, every key, equally likely.) Let T(I) be the running time on input I. The average-case cost is the expected value

T_{\text{avg}}(n) \;=\; \mathbb{E}[T] \;=\; \sum_{I:\,|I|=n} \Pr[I]\cdot T(I).

Written like that it looks hopeless — the sum ranges over an exponential number of inputs. The trick is never to evaluate it directly. Instead we break T into a sum of tiny pieces, take the expectation of each piece, and add them back up. That is where linearity earns its keep.

For any random variables X_1,\dots,X_n, \;\mathbb{E}\!\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i].
It holds whether or not the X_i are independent — this is the magic. No independence, no product rule, no joint distribution needed.
Constants pull out: \mathbb{E}[aX + b] = a\,\mathbb{E}[X] + b.

Indicator random variables — the workhorse

An indicator for an event A is the variable

X_A = \begin{cases} 1 & \text{if } A \text{ happens},\\ 0 & \text{otherwise.}\end{cases}

Its expectation is not something to compute — it simply is the probability of the event: \mathbb{E}[X_A] = 1\cdot\Pr[A] + 0\cdot\Pr[\lnot A] = \Pr[A]. The whole method is a three-step ritual:

Decompose. Write the quantity you care about as a sum of indicators, X = \sum_i X_i (each X_i a yes/no event).
Apply linearity. \mathbb{E}[X] = \sum_i \mathbb{E}[X_i] = \sum_i \Pr[X_i = 1].
Compute each probability. Usually a one-line combinatorial argument, then sum.

The beauty is that the individual events are often correlated in a knotted, terrifying way — and it does not matter, because linearity never asked about independence.

Worked example 1 — expected length of a hash-table chain

Throw n keys into a hash table with m slots under simple uniform hashing, so each key lands in a uniformly random slot. What is the expected number of keys sharing a fixed slot s? Let X_i = 1 iff key i hashes to s. Then \Pr[X_i = 1] = 1/m, so

\mathbb{E}\!\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n}\frac{1}{m} = \frac{n}{m} = \alpha,

the load factor. So an unsuccessful search touches on average 1 + \alpha elements — constant time whenever m = \Theta(n). That single line is the entire justification for why hashing is "O(1) on average".

Worked example 2 — the hiring / records problem

You interview n candidates in random order, and every time you meet someone better than everyone so far, you (expensively) hire them. How many times do you hire? Equivalently: as you scan a random permutation, how many left-to-right maxima (running records) do you see? Let X_i = 1 iff candidate i is the best of the first i seen. Among those first i candidates, each is equally likely to be the largest, so

\Pr[X_i = 1] = \frac{1}{i} \quad\Longrightarrow\quad \mathbb{E}[\text{hires}] = \sum_{i=1}^{n}\frac{1}{i} = H_n \approx \ln n + \gamma.

So out of a hundred candidates you hire only about \ln 100 + 0.577 \approx 5.2 times, not fifty. The harmonic number H_n grows like \ln n — punishingly slowly. The chart shows how few records appear even as n soars.

The same H_n \approx \ln n resurfaces in the average number of comparisons in a successful binary-search-tree search on random keys, and — as you will see next — in the expected depth of randomised quicksort. It is one of the most important sums in the analysis of algorithms.

Worked example 3 — expected comparisons, and the danger of averaging the wrong thing

Consider a naive linear search for a key that is present, at a uniformly random position among the n slots. It examines k elements when the key sits at position k, each position equally likely, so

\mathbb{E}[\text{comparisons}] = \sum_{k=1}^{n} k\cdot\frac{1}{n} = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}.

On average you scan about halfway — exactly the intuition, now proved. Note the assumption did real work: change the distribution (say, keys near the front are searched more often) and the average changes. The answer is only ever meaningful relative to the input distribution you assumed.

Quantity	Decomposition	Expectation
Keys in a hash slot	\sum_i \mathbf{1}[\,h(i)=s\,]	n/m = \alpha
Hires (records)	\sum_i \mathbf{1}[\,i\text{ is a running max}\,]	H_n \approx \ln n
Linear-search compares	\sum_k k\cdot\mathbf{1}[\text{key at }k]	(n+1)/2
Fixed-point permutations	\sum_i \mathbf{1}[\pi(i)=i]	1

That last row is a party trick: a random permutation of n items has, on average, exactly one fixed point, for every n — because each of the n positions is fixed with probability 1/n, and n\cdot(1/n)=1. No independence required; linearity does it in a breath.

There are two ways to inject randomness, and they are often confused. Average-case analysis averages over a distribution on inputs — you assume the world hands you random data, and a clever adversary who knows your code can still pick a bad input. A randomised algorithm, by contrast, flips its own coins: the input can be anything, even adversarial, and the expectation is taken over the algorithm's internal randomness. The maths — linearity, indicators — is identical, but the guarantee is far stronger, because the adversary cannot see your coins. Randomised quicksort turns quicksort's fragile average-case bound into one that holds on every input.

A seductive shortcut: "the average input is half-sorted, and quicksort on a half-sorted array takes c steps, so the average time is c." This is wrong, and the error is deep. \mathbb{E}[T(I)] averages the running time over inputs; T(\mathbb{E}[I]) runs the algorithm on some "average input" — a different number entirely, and often not even well-defined. In general \mathbb{E}[f(X)] \neq f(\mathbb{E}[X]) unless f is linear (Jensen's inequality is the precise statement). Always average the cost, never invent a typical input and time that. Decompose into indicators and let linearity do the work.