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

$\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
4
$\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

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

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.