2,249 views
1 votes
1 votes
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.

2 Answers

Best answer
5 votes
5 votes

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

selected by
0 votes
0 votes
(n+1)/2

Related questions

1 votes
1 votes
1 answer
1
Sahil Gupta asked Nov 25, 2014
1,967 views
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 numbe...
1 votes
1 votes
0 answers
2
Sahil Gupta asked Nov 25, 2014
742 views
Answer the following part:a) Show that, under the assumption that the input is equally likely to be any of the n! permutations of theseintegers, the average number of com...
0 votes
0 votes
1 answer
3
dhruba asked Jun 5, 2023
411 views
Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...