in Algorithms reopened by
837 views
5 votes
5 votes

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1...n]$ having $n$ values : 

  1. Sequentially choose $i$ from 1 to n 
  2. if A[i] = x then Stop else Goto 1

Let $x$ be present in A two times, what is the expected no of comparisons made by the algorithm before it terminates for $n=5$? 

in Algorithms reopened by
by
837 views

2 Comments

@Bikram Sir

from where u took this question?
0
0
here he is asking expected no. of comparison that means we can also call it average no. of comparison so here max 4 possible and total com 1+2+3+4=10

and avg for 5 element 10/5 =2 is it not correct way ??? please response any 1 who have exact idea.
0
0

2 Answers

13 votes
13 votes
Best answer

Since $x$ is present in the array we can assume each of the $n$ places have same probability of being $x$. We are told that there are two $x$ in the array. So, for $n=5$, probability of position $i$ being $x = \frac{2}{5}$ for $ i = 1..5$. Also, since $x$ is present in the array two times, we never will have 5 comparisons.

Expected number of comparisons

$= 1 \times \frac{2}{5} + 2 \times \frac{3}{5} \times \frac{2}{5} + 3 \times {\frac{3}{5}}^2 \times \frac{2}{5}   + 4 \times {\frac{3}{5}}^3 \times \frac{2}{5}  \\
= \frac{2}{5} \left[1 + 2 \times 0.6 + 3 \times 0.6^2\right] + 4 \times 0.6^3 \\
=0.4 \left[1 + 1.2 + 1.08\right] +  0.864 \\
=2.176$


The above answer is wrong because it did not consider uniform probability distribution and simply considered a probablity for each position. In correct way,

Expected number of comparisons

$= 1 \times \frac{2}{5} + 2 \times \frac{3}{5} \times \frac{2}{4} + 3 \times {\frac{3}{5}} \times \frac{2}{4} \times \frac{2}{3}  + 4 \times {\frac{3}{5}} \times \frac{2}{4}\times \frac{1}{3}  \\
= 0.4 + 0.6 + 0.6 + 0.4 \\= 2.$

edited by
by

4 Comments

@Arjun SIR https://gateoverflow.in/840/gate2002-2-10 HERE INN THIS QUESTION YOU DID NOT CONSIDER UNIFORM DISTRIBUTION??

1
1
That is random scan which means with repetition. Here it is sequential scan.
1
1
ONCE WE CHOOSE i=1 suppose we dont get element at a[1]

then we will choose i=2 and and search at a[2] ??

is it correct??
0
0
3 votes
3 votes
Let X be no. of comparisons.

N=5 given and X is present in array 2 times.

so probable positions X can be is in 5C2 ways.x can be present at

(1,2) , (1,3), (1,4), (1,5)

(2,3) ,(2,4) ,(2,5)

(3,4), (3,5)

(4,5)

total 10 ways.

If x=1 means x found at location 1 therefore comparisons required is 1. Also probablity x present at 1 is 4/10.

so

E(X)=$1* \frac{4}{10} + 2* \frac{3}{10} + 3*\frac{2}{10} + 4*\frac{1}{10} = \frac{20}{10}=2$
Answer:

Related questions