3
$\begingroup$

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!

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

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You are right. In CLRS which I am reading, they said that there is an equal probability for each element in the list to be the required element, but additionally also assumed without indicating that the required element will definitely be in the list. Thank you :) $\endgroup$ – Yiyuan Lee Mar 15 '17 at 6:31
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What about the case where required element is not in the list at all? $\endgroup$ – Yiyuan Lee Mar 15 '17 at 6:10
  • 1
    $\begingroup$ @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$. $\endgroup$ – D.W. Mar 15 '17 at 17:48
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.