Question

Suppose that the probability that x is in a list of n distinct integers is 2/3 and that it is equally likely that x equals any element in the list. Find the average number of comparisons used by the linear search algorithm to find x or to determine that it is not in the list.

Answer 1

$\text{Expected number of comparisons} = \\ \sum_{i=1}^n \left ( \text{number of comparison till }i^{th} \text{ entry}  \\ \times \text{ probability of getting the number at } i^{th} \text{ entry}\right) \\ + \frac{1}{3} . n $

The last $\frac{1}{3} n$ is for the case when $x$ is not in the list.

Probability of $x$ being in the list = 2/3

Since it is equally likely that $x$ is any element in the list, probability that $x$ is element $i$ is $\frac{2}{3n}$

So,

$\text{Expected number of comparisons} = \sum_{i=1}^n \left(i . \frac{2}{3n} \right) +\frac{n}{3} \\= \frac{ n+1}{3} + \frac{n}{3} \\= \frac{2n+1}{3}$

Now, there is a catch here. We have counted one comparison for one element in the linear list. But if we count the loop exit condition and the final found or not check also as in the algorithm give here http://www.programmingsimplified.com/c/source-code/c-program-linear-search, we get $2i + 1$ comparisons for a successful check at $i^{th}$ position and $2n+2$ comparisons if $x$ is not in the list. This would give

$\text{Expected number of comparisons} = \sum_{i=1}^n \left((2i +1) . \frac{2}{3n} \right) +\frac{(2n+2)}{3} \\= \frac{2.( n. (n+1) + n)}{3n} + \frac{2n+2}{3}  \\= \frac{2n+4}{3} + \frac{2n+2}{3}\\= \frac{4n+6}{3}$

Comments

Sir.. you have added 1/3.n for the case when x is not in the list..why so?

---

1/3 is the probability of x not in the list as given in question.