One algorithm, many running times
In the last guide we learned to measure cost by counting basic steps in the RAM model. But here is a surprise that trips up almost everyone at first: a single algorithm does not have a single step count. It has a different count for every input you feed it. Fix the input size at, say, n = 1000, and there are still astronomically many distinct inputs of that size — and the algorithm may race through some of them and crawl through others.
Take a tiny example: searching a list of n numbers from left to right for a target. If the target sits in the very first slot, the loop stops after one comparison. If it sits in the last slot, or is missing entirely, the loop grinds through all n slots. Same algorithm, same n — but the work ranges from 1 step to about n steps depending only on which input you handed it. So the question "how many steps does linear search take on a list of size n?" has no single answer. We need a way to collapse a whole family of inputs into one clean claim.
The trick is to stop asking about one input and start asking about all inputs of size n at once. Among that whole family, we can pick out the most expensive one, the cheapest one, or a typical one. Those three choices are exactly the worst case, the best case, and the average case. Each turns the messy cloud of per-input costs into a single function of n that we can then compare across algorithms.
The worst case: the promise you can keep
The worst-case running time is the maximum number of steps over all inputs of size n. Write it as a function W(n): for each n, look at every input of that size and take the largest cost. For linear search, the worst input is one where the target is last or absent, so W(n) is about n steps. This is the most important lens in the whole subject, and the reason is simple: it is a guarantee. If the worst case is W(n), then no input of size n can ever make the algorithm slower than that. It is a promise you can keep to every user, no matter how adversarial their data.
That guarantee is why, by default, "the running time of algorithm X" means its worst case unless someone says otherwise. It is also the case an adversary cannot beat: imagine an opponent who gets to choose your input after seeing your code, trying to make you slow. The worst case is exactly the cost of their best attack. For anything where a slow response is unacceptable — a flight controller, a payment system, a real-time game loop — the worst case is the number that actually matters, because the cheap inputs do not save you on the day the expensive one arrives.
Best case: useful as a floor, dangerous as a brag
The best-case running time B(n) is the minimum over all inputs of size n — the cost on the single luckiest input. For linear search, B(n) is constant: the target happens to sit first, so we stop after one comparison. Best case is the natural counterpart to worst case, and it does carry honest information: it tells you the algorithm cannot possibly be faster than B(n), a genuine floor on its cost.
But the best case is the most over-sold and least trustworthy of the three as a description of real performance. It is achieved by exactly one lucky kind of input, and you almost never get to choose your inputs. A famous trap: insertion sort runs in about n steps on an already-sorted array — a beautiful linear best case — but on a reverse-sorted array it takes about n^2 steps. Quoting the n best case as if it described the algorithm would be deeply misleading. Best case is honest as a floor; it is a lie when paraded as a summary.
Average case: honest only about its assumptions
The average-case running time A(n) is the expected number of steps when the input is drawn at random — the average cost weighted by how likely each input is. It is often the most realistic picture of day-to-day behaviour. But it hides a load-bearing assumption that you must state out loud: *random according to which distribution?* The average is taken over an assumed probability distribution on inputs, and change that distribution and the average changes with it. There is no such thing as "the" average case in a vacuum.
Make this concrete with linear search again. Suppose the target is present and equally likely to be in any of the n positions. Then the work is 1 step if it is first, 2 if second, and so on up to n, and the average is (1 + 2 + ... + n) / n = (n + 1) / 2, about n/2 steps. So under that uniform assumption the average is half the worst case. But if in your real workload the target is usually near the front, the true average is far smaller — and if it is usually missing, the average climbs back toward n. The number is only as trustworthy as the distribution you assumed to compute it.
When the three diverge: the quicksort cautionary tale
For some algorithms all three lenses agree, and life is simple. Merge sort, for instance, always splits cleanly and does about n log n work no matter the input, so best, average, and worst all sit at Theta(n log n). When the cases agree, you can quote one number with a clear conscience. The interesting algorithms are the ones where the three lenses tell sharply different stories.
Plain quicksort (with a fixed pivot, say always the last element) is the classic example. Its best and average cases are a lovely Theta(n log n), but its worst case — handed an already-sorted array — degrades to Theta(n^2), because every partition peels off just one element and the recursion becomes a slow, lopsided chain. So which case you cite changes the verdict completely. Reporting only quicksort's average would hide a real n^2 cliff that a malicious or merely unlucky input can walk you off of.
Best / average partition: T(n) = 2 T(n/2) + O(n) -> Theta(n log n) Worst partition: T(n) = T(n-1) + O(n) -> Theta(n^2)
Choosing your lens honestly
So which case should you report? It depends on the promise you need to make, and a careful analysis often quotes more than one. Here is a sensible default order of attack.
- Start with the worst case. It is the guarantee, the adversary-proof number, and the default meaning of "running time." If the worst case is good enough, you may not need to look further.
- If the worst case is scary but rare, reach for the average case — and name your distribution. State out loud what "random input" means here, and check whether your real workload actually matches it. An unstated distribution makes the average meaningless.
- Treat the best case as a floor, never a summary. Use it to argue "nobody can do better than this on the lucky input," but never quote it as the algorithm's speed.
- When the gap is dangerous, redesign rather than report. Quicksort's n^2 worst case is why people randomize the pivot or switch algorithms — sometimes the right move is to make the bad case go away, not just disclose it.
One last honest caveat, the same one that haunts all of cost analysis: even after you pick a case, the resulting function is usually quoted with asymptotic notation, which deliberately drops constants and low-order terms. So a worst case of Theta(n^2) and a worst case of Theta(n log n) describe how cost scales, not a verdict at every size — for small enough n the n^2 method can still win. The worst/best/average lens tells you which input you are measuring; asymptotics tells you how that cost grows; and only together, with their assumptions stated, do they add up to an honest claim. That pairing is exactly what the next rung is about.