Question

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!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top