reopened by
1,437 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$? 

reopened by

2 Answers

Best answer
13 votes
13 votes

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
4 votes
4 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

2 votes
2 votes
2 answers
1
Bikram asked Oct 4, 2016
345 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
2 votes
2 votes
1 answer
3
Bikram asked Oct 4, 2016
537 views
While inserting keys 12,44,13,88,23,94,11,39,20,16 and 5 in a 11 item hash table using the hash function $h(i) = (2i+5) \mod 11$, total number of collisions that occur ...
2 votes
2 votes
2 answers
4
Bikram asked Oct 4, 2016
543 views
Consider the following recurrence relation.$$T(n) = \begin{cases}1 & \quad if \: n = 1 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$$What will be the value of $T(10)$?