Average Case Analysis

Most inputs are neither the best case nor the worst case. Average-case analysis asks about the time complexity of a typical input. It is the work an algorithm does, averaged over all the inputs of size $n$ .

To average, we have to decide how much each input counts, which inputs are common and which are rare. So to talk about the average case, we need to make an assumption about the distribution of inputs. In other words, we need to say which inputs are likely to occur.

To see how this works, let’s do average-case analysis on linear search.

Suppose the target is present, and assume it is equally likely to sit at any of the $n$ positions. If it sits at position 1, we do 1 comparison; at position 2, we do 2; and so on up to $n$ comparisons if it sits at the last position. Notice that we had to assume something to get this far: that the $n$ positions are equally likely. Averaging over those $n$ positions gives

\frac{1 + 2 + \dots + n}{n} = \frac{n ( n + 1 ) /2}{n} = \frac{n + 1}{2}

The numerator uses the fact that $1 + 2 + \dots + n = n (n + 1) /2$ , the sum of the first $n$ positive integers.

So a typical successful search costs about $n /2$ comparisons, roughly half the positions in the array. That differs from the worst case of $n$ comparisons, but Big-Oh ignores the difference. We suppress coefficients, so $n /2$ is still $O (n)$ . So for linear search, the average case and the worst case are in the same Big-Oh class.

That is one reason most programmers default to worst-case analysis: for the algorithms we study, the average case is usually in the same Big-Oh class anyway. Another reason is the guarantee we saw earlier: the worst-case bound holds for every input of size $n$ . A third is that the average case needs an assumption about the distribution of inputs, and it is usually more work to compute. So, in this course, we use worst-case analysis.