T(n): best case, worst case, average case

The same procedure on two inputs of the same size can do wildly different amounts of work, so cost is not one number but three.

Searching a list for a value can be over immediately or can take the whole list. Nothing about the length of the list decides which. That is the first complication in measuring cost, and it has to be dealt with before any notation is worth learning.

Here is a left-to-right search that counts the comparisons it makes. The same list is searched four times, for four different values.

The costs are 1, 3, 6 and 6. The list never changed length. What changed is where the answer was, and the search stops the moment it finds it, so the position of the target is what decides the work.

Input size, and the function T

The input size, written $n$, is the measure of how big the input is. For a list it is the number of entries. For a piece of text it is the number of characters. For a single number it is usually the number of bits needed to write that number down, because that is how much has to be read.

Once the size is fixed there is still a set of possible inputs, so cost is not one number. Write $T(n)$ for the number of primitive operations the algorithm performs. Three different functions can be meant by that, and they are not interchangeable.

• Best case: the smallest number of operations over all inputs of size $n$. For the search, 1 comparison, when the target sits first.
• Worst case: the largest number of operations over all inputs of size $n$. For the search, $n$ comparisons, when the target sits last or is absent.
• Average case: the mean number of operations over inputs of size $n$, weighted by how likely each input is. That last clause is not optional. Without a stated distribution over inputs, the phrase has no meaning.

Here is the average worked out for the search, under one explicit assumption: the target is present, and it is equally likely to be at any of the $n$ positions. Then the cost is $k+1$ comparisons when the target sits at position $k$, and each position has probability $1/n$.

One new symbol appears in the line below. The capital Greek letter sigma, $\sum$, means add up what follows once for each value of the counter written underneath it, starting at the value it is set to there and finishing at the value written on top. So $\sum_{k=0}^{3} k$ means $0 + 1 + 2 + 3$, which is 6.

The middle step used a fact worth keeping: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$. To see why, write the sum forwards and again backwards underneath it, $1 + 2 + \cdots + n$ over $n + (n-1) + \cdots + 1$. Each of the $n$ columns adds to $n + 1$, so the two copies together come to $n(n+1)$, and one copy is half of that. With $n = 6$: $1+2+3+4+5+6 = 21$, and $\frac{6 \cdot 7}{2} = 21$.

For a list of 6 that is 3.5 comparisons, which is close to the 1, 3, 6 you saw. Change the assumption and the answer changes with it: if the target is absent nine times out of ten, the average is much nearer $n$. The number is only as good as the distribution it came from.

Counting a nested loop

Insertion sort makes the gap between the three cases much wider. The inner loop shifts entries while they are bigger than the value being placed, so an array that is already in order does almost nothing and one in reverse order does everything.

On eight entries the counts are 7, 28 and something in between. Both extremes can be derived on paper rather than measured, and doing so is the point of the exercise.

In the best case every value is already at least as large as the one before, so for each $i$ the inner loop makes one comparison and stops. There are $n-1$ values of $i$, so the count is $n-1$. With $n = 8$ that is 7, which is what printed.

In the worst case every value is smaller than everything before it, so for each $i$ the inner loop compares against all $i$ entries to its left and shifts every one of them. That gives $1 + 2 + \cdots + (n-1)$ comparisons in total.

The average for insertion sort comes from the same style of argument: for a randomly ordered array, the value being placed lands on average about halfway into the sorted part, so it is compared with about half of it, which halves the worst-case count.