Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $n$ cases corresponding to when the target value is the $1$st, $2$nd, ..., $n$th entry of the list. There is also the case where the entry is not in the list at all, so we have $n + 1$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $1, 2, \dots, n$ comparisons respectively. For the case where the target value is not in the list, we need $n$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $\frac{n}{2}$.

May I where is the fallacy in my reasoning? Thank you!

• Because of the extra case when the required element is not in the list at all. – Yiyuan Lee Mar 15 '17 at 6:14

It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a probability distribution for the input. As an example, it is well known that the average running time of naive quicksort is $\Theta(n \log n)$, but that result is dependent on assuming that the input arrays are uniformly distributed over the elements of the symmetric group of size $n$. If we choose different distributions, the result changes reflecting our choice.
Intuitively, if the input distribution is such that you expect to miss almost every time, your average number of comparisons will be very close to $n$.
Let us assume that required element is equally likely to be in any position between $1$ and $n$. Let $x _i$ be a random variable. Random variable $x_i = 1$ means required element is in ith position and vice-versa. Now probability that required element is in position between $1$ and $n$ is $$Pr[x_i = 1] = \frac{1}{n}$$ Now Expected value is given by $$\mathbb{E}(x) = 1 \times\frac{1}{n} + 2 \times \frac{1}{n} + 3 \times \frac{1}{n} +\cdots + n \times\frac{1}{n}$$ which can be written as $$\mathbb{E}(x) = \frac{n(n+1)}{2n} = \frac{(n+1)}{2}$$ which is a required answer
• @YiyuanLee, This analysis assumes that case will never happen. In other words, this analysis is only applicable in situations where you can be guaranteed that the required element is always in the list. (An assumption is something that narrows the applicability of an answer to only those situations that happen to satisfy the assumption.) If you have a situation where the required element might or might not be in the list, then this answer is not applicable and the average running time might not be $(n+1)/2$. – D.W. Mar 15 '17 at 17:48