The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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.

asked in Probability by Active (1.7k points) | 606 views

1 Answer

0 votes
Best answer

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


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

answered by Veteran (348k points)
selected by
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,239 questions
40,932 answers
39,846 users