Best, Worst and Average Case

The same algorithm can be lightning-fast on one input and crawl on another. Insertion sort skims through an already-sorted array but grinds through a reversed one; linear search may hit its target on the first probe or the last. So "how long does it take?" has no single answer for a given size n — it has a range, one number per possible input. To report a single running time we choose a lens onto that range: the best, worst, or average case.

These three are not competing definitions of speed — they answer three different questions. This page is about choosing the right lens, and about the single most common confusion in all of complexity: the lens (which input) is a completely separate axis from the asymptotic bound (which direction) you attach to it.

The three lenses

Fix an input size n and let T(x) be the running time on a specific input x of that size. The three lenses are three ways to summarise T over all inputs of size n:

Worst case — \displaystyle T_{\text{worst}}(n) = \max_{|x| = n} T(x). The slowest the algorithm can possibly be. A guarantee: it will never be worse than this.
Best case — \displaystyle T_{\text{best}}(n) = \min_{|x| = n} T(x). The fastest it could ever be. A promise you can't rely on: it needs a lucky input.
Average case — \displaystyle T_{\text{avg}}(n) = \mathbb{E}_{x \sim \mathcal{D}}[\,T(x)\,], the expected running time when the input is drawn from a distribution \mathcal{D}. Typical behaviour — but only for that assumed distribution.

The three lenses form an ordering for every n:

T_{\text{best}}(n) \;\le\; T_{\text{avg}}(n) \;\le\; T_{\text{worst}}(n).

For linear search over n elements these three curves fan out cleanly — a constant floor, a line through the middle, and a line at the top:

Why worst case is the default guarantee

Unless stated otherwise, "the running time of algorithm A" means its worst case. There are three good reasons the field settled on this lens:

It's a real guarantee. A worst-case bound holds for every input — no adversary, no unlucky data set, can ever beat it. That is exactly what you want when a missed deadline crashes an aircraft or a trade.
It needs no assumption about inputs. Average case demands you commit to a distribution \mathcal{D}; worst case commits to nothing and so can never be wrong about the inputs you'll actually see.
It composes. Plug a worst-case-T subroutine into a loop and you can safely multiply; expected costs don't chain so cleanly.

Best case, by contrast, is almost always misleading: every algorithm has a lucky input, so "runs in \Theta(n) in the best case" tells you nothing about the input you actually hold. Quoting a rosy best case to sell an algorithm is a classic sleight of hand — bogosort's best case is \Theta(n) (the array happens to arrive sorted), yet no one would call it a good sort.

Average case: expectation over a distribution

The average case is the most informative and the most treacherous lens, because its answer depends entirely on the distribution \mathcal{D} you assume. "Average" is not a property of the algorithm alone — it is a property of the algorithm plus a model of its inputs. State the distribution or the number is meaningless.

The showcase is sorting-style analysis on quicksort. With a fixed pivot rule, an adversary can force \Theta(n^2) (feed it sorted data). But over a uniformly random permutation of the inputs, the expected number of comparisons is T_{\text{avg}}(n) = \Theta(n \log n), and the analysis runs straight through the harmonic sum H_n = \Theta(\log n) — element i and element j are compared with probability 2/(j-i+1), and summing those probabilities gives the n \log n. That single result — a worst-case-n^2 algorithm that is n \log n on average and blazingly fast in practice — is why the full average-case analysis earns a page of its own later in the course.

Because the worst case can be pessimistic to the point of dishonesty. Quicksort and the simplex method for linear programming both have exponential-or-quadratic worst cases that essentially never occur on real data — insisting on the worst case would have you reject two of the most successful algorithms ever written. Hash tables are \Theta(n) per lookup in the worst case (every key collides) yet \Theta(1) on average, which is the only reason we use them everywhere. Average case is how we explain the gap between a scary worst case and superb real-world performance — and randomised algorithms go one better, shuffling their own input so the good "average" holds no matter what the adversary sends.

The deepest confusion in this whole subject: best/worst/average (which input you measure) is a completely separate axis from $O$/$\Omega$/$\Theta$ (which direction you bound). You can attach any bound to any case. It is perfectly sensible to say insertion sort's worst case is \Theta(n^2) and \Omega(n^2) and O(n^2) — three bounds on one case. It is equally sensible to bound its best case as \Theta(n). The sentence "the algorithm is O(n^2)" does not mean "worst case", and "\Omega" does not mean "best case" — a lower bound can be on the worst case too (insertion sort is \Omega(n^2) in the worst case). Say both coordinates: "worst-case \Theta(n^2)", "best-case \Theta(n)". Anyone who conflates the two axes will eventually prove something false.

Worked example — linear search

Search an unsorted array of n elements for a target, scanning left to right.

function linearSearch(a: number[], target: number): number { for (let i = 0; i < a.length; i++) { if (a[i] === target) return i; // stop as soon as we find it } return -1; // not present }

Best case: the target is at index 0 — one comparison, \Theta(1).
Worst case: the target is last or absent — n comparisons, \Theta(n).
Average case: if the target is present and equally likely to be at any of the n positions, the expected number of comparisons is \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2} = \Theta(n).

So best case is \Theta(1) but both worst and average are \Theta(n) — halving the constant (n vs (n+1)/2) doesn't change the class. This is typical: the average often shares the worst case's growth rate, differing only in the constant, which is why the worst-case guarantee is usually a fair summary anyway.