Best, Average, and Worst Case - PCCST303

Why input size alone is not the whole story

So far, T(n) has been treated as depending only on n, the input size. But two inputs of the exact same size can make an algorithm do very different amounts of work, depending on what is actually inside them, not just how many elements there are.

Take linear search over this array:

01234

n is 5 either way, but searching for 10 and searching for 50 are not the same amount of work.

Best, worst, and average case

Best case: searching for 10

Definition

Best case is the minimum work an algorithm does for any input of a given size.

01234

Searching for 10 finds it immediately, at the very first position checked. Only one comparison is needed. This is the best case: O(1).

Worst case: searching for 50

Definition

Worst case is the maximum work an algorithm does for any input of a given size.

01234

Searching for 50 means every earlier element (shown dimmed) has to be checked and ruled out before reaching it. All n elements are inspected. This is the worst case: O(n). If the target were not in the array at all, the search would still have to check all n elements before it could conclude that, which is also the worst case.

Average case

Definition

Average case is the expected work an algorithm does, averaged over all possible inputs of a given size.

This is usually the least intuitive of the three, because it is not about one specific input like best and worst case are. It is a summary over every possible input.

Assume the target is equally likely to be at any of the 5 positions in the array. Linear search checks position 0, then 1, then 2, and so on, stopping as soon as it finds a match. So the number of comparisons needed depends entirely on which position holds the target:

That row shows, for each position, how many comparisons it would take to find the target if it were sitting there: position 0 needs 1 comparison, position 1 needs 2, and so on up to position 4 needing 5.

To get the average, add up all of these possible comparison counts and divide by how many positions there are:

$\text{average} = \frac{1 + 2 + 3 + 4 + 5}{5} = \frac{15}{5} = 3$

So on average, linear search over this array takes 3 comparisons, roughly the middle of the array, which matches the intuition that on average you have to search about halfway through before finding what you are looking for.

Generalizing this to any size n: the total comparisons across all n equally likely positions is $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ , and dividing by n positions gives $\frac{n+1}{2}$ , roughly n/2. The constant factor of 1/2 does not change the growth rate, so the average case is still O(n), the same order as the worst case, just with a smaller constant in front.

Note

It is tempting to guess that average case = (best case + worst case) / 2, but that is not what average case means, and it does not generally hold. Average case is the expected work over the actual distribution of possible inputs, here, averaging the comparison count across every position the target could be at. It only happens to land near the midpoint for linear search because each position is equally likely and the comparison counts increase steadily from 1 to n. For other algorithms, the average case can be much closer to the best case, much closer to the worst case, or something not expressible as a simple average of the two at all.

Key Idea

Best, worst, and average case are not different algorithms, they are the same algorithm evaluated under different assumptions about the input. When no case is specified, "the time complexity of an algorithm" usually means the worst case, since that is the guarantee you can actually rely on: the algorithm will never take longer than that, no matter what input it receives.

Quick recall

The same algorithm can take different amounts of work on inputs of the same size, depending on what the input actually contains.
Best case: minimum work (the most favorable input). Worst case: maximum work (the least favorable input). Average case: expected work across all possible inputs.
For linear search, the best case is O(1) (found immediately) and the worst case is O(n) (checked every element, or confirmed absence).
Worst case is the default when a time complexity is stated without qualification, because it is the only case that guarantees an upper limit on the work done.