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.
$\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}$
23386 Points
17068 Points
8158 Points
6286 Points
5438 Points
4978 Points
4772 Points
4344 Points
3964 Points
3804 Points
Gatecse
X->YZ , Y->XZ , ...