1,802 views
Suppose the probability that x is the ith element in a list of n distinct integers is i/[n(n + 1)]. 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.

Expected number of comparisons = sum((number of comparison till ith entry) * probability of getting the number at ith entry) + n. probability that $x$ is not in the list.

Probability that $x$ is in the list = $\sum_{i=1}^n \frac{ i} {n.(n+1)} = \frac{1}{2}$

So, probability of $x$ not in the list $= \frac{1}{2}$

Thus, Expected number of comparisons

$= \sum_{i=1}^n \frac{ i} {n.(n+1)} . i + \frac{n}{2}\\= \sum_{i=1}^n \frac{i^2}{n. (n+1)} + \frac{n}{2} \\= \frac{2n+1}{6} + \frac{n}{2} \because \sum_{i=1}^n i^2 = \frac{n.(n+1).(2n+1)}{6} \\= \frac{5n + 1}{6}$

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 \frac{ i} {n.(n+1)} . (2i+1) + \frac{2n+2}{2}\\= \sum_{i=1}^n \frac{2i^2 + i}{n. (n+1)} +(n+1) \\= \frac{2n+1}{3} + \frac{1}{2} + (n+1) \\= \frac{5n+4}{3} + \frac{1}{2} = \frac{10n + 11}{6}$

by

why have you multiplied probability of x not in the list with 'n',in your first calculation??
After comparing all elements of the list with x, we can say that x is not in the list. In this process, we performed n number of comparisons. That is why 'n' is multiplied when x is not in the list
ooh.alright.thanks
(n+1)/2
by

@Akshay007
Approch?

total comparison for n elements =n*(n+1)/2 ... On an average divide by n .. You get n+1/2

1 vote
1
1,531 views
1 vote