worst-, best- and average-case

Two inputs of the very same size can take an algorithm wildly different amounts of work, so a single number rarely tells the whole story. Imagine looking for a name in an unsorted list: if it happens to be first, you find it instantly; if it is last or missing, you scan the whole thing. Worst-, best-, and average-case are three honest lenses on this spread — the slowest an input of size n can be, the fastest it can be, and what you would expect on a typical input.

Fix the input size at n and look at all instances of that size. The worst-case running time is the maximum work over all those instances — the gloomiest input. The best-case is the minimum — the luckiest input. The average-case is the mean, computed over some assumed probability distribution of inputs. Linear search makes this concrete: best-case it does 1 comparison (target is first), worst-case it does n comparisons (target is last or absent), and if the target is equally likely to be in any of the n positions, the average is about n/2 comparisons. All three describe the same algorithm; they just ask different questions about it.

Worst-case is the default in practice because it is a guarantee: "never slower than this, whatever the input," which is what you want for anything with a deadline. Best-case is mostly a curiosity — it tells you the floor, not what to count on. Average-case is genuinely useful but comes with a sharp caveat: it depends entirely on the assumed distribution of inputs, and if real inputs do not match that assumption, the average can mislead. There is also a subtle cousin, expected time for randomized algorithms, where the averaging is over the algorithm's own coin flips rather than over the inputs — randomized quicksort is O(n log n) expected this way, yet its worst case is still O(n^2). Naming which lens you are using is essential; a bare "this is O(n log n)" is ambiguous until you say worst-case, average-case, or expected.