from where u took this question?

Dark Mode

837 views

5 votes

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

- Sequentially choose $i$ from 1 to n
- 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$?

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

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

1

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$

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$