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

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!

Answer 1

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.

Therefore, it is impossible to give a reasonable answer to your question without making assumptions of statistical nature on what queries you expect. In particular, the average number of comparisons is deeply impacted by what is the ratio of the inputs for which the search fails to find a matching element.

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$.

Answer 2

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

Reference : https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node56.html

Answer 3

Let us assume that we are given a real number $x$ and a list of $n$ distinct real numbers. The linear search algorithm, described below,

   linearsearch(x, a1,a2,...an):

        i:=1
        while(i<=n and x not equal to ai):
              i:=i+1
        if i<=n:
             loc:=i
        else:
             loc:=0

locates $x$ by successively comparing it to each element in the list, terminating when $x$ is located or when all the elements have been examined and it has been determined that $x$ is not in the list.

What is the average-case computational complexity of the linear search algorithm if the probability that $x$ is in the list is $p$ and it is equally likely that $x$ is any of the $n$ elements in the list? (There are $n + 1$ possible types of input: one type for each of the $n$ numbers in the list and a last type for numbers not in the list, which we treat as a single input.)

Now $i$ comparisons are used if $x$ equals the $i$ th element of the list and, there are $n$ comparisons are used if x is not in the list. The probability that $x$ equals $a_i$ , the $i$ th element in the list, is $\frac{p}{n}$, and the probability that $x$ is not in the list is $q = 1 − p$.

It follows that the average-case computational complexity of the linear search algorithm is

$$E= \frac{p}{n} + \frac{2p}{n} +···+ \frac{np}{n} + nq$$

$$= \frac{p}{n}(1+2+···+n) + nq$$

$$= \frac{p}{n}.\frac{n(n+1)}{2}+nq$$

$$= p.\frac{n+1}{2}+nq$$

Now if we plug in the probability that

$$p = \frac{n}{n+1}$$ and hence $$q=\frac{1}{n+1}$$ then

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

Now again if we plug in,

$$p=1$$ and hence $$q=0$$ then we have,

$$E= 1.\frac{n+1}{2}+n.0 = \frac{n+1}{2} $$