GATE CSE 2002 | Question: 2.10

Question

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

1. Choose an $i$ at random from $1..n$
2. If $A[i] = x$, then Stop else Goto 1;

Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates?

• A. $n$
• B. $n-1$
• C. $2n$
• D. $\frac{n}{2}$

Comments

Hi can u tell why e+1 is multiplied on failure

---

https://gateoverflow.in/840/gate2002-2-10?start=5

---

Let X be the expected no. of comparisons.
X=(Probability of success)*1 + (Probability of Failure)*(X+1)
X=(1/n)*1 + ((n-1)/n)*(X+1)
After solving this, X=n

Answer 1

Expected number of comparisons $(E) = 1 \times $ Probability of find on first comparison $+ 2 \times $Probability of find on second comparison $+ ... + i \times $ Probability of find on ith comparison $+ ...$

$= 1 \times \frac{1}{n} + 2 \times \frac{n-1}{n^2}  + 3 \times \frac{ (n-1)^2}{n^3} + \dots $

$ =  \frac{1/n} {1 - \frac{n-1}{n} } + \frac{(n-1)/n^2}{\left( {1- \frac{n-1}{n} }\right)^2} \\ \left( \text{Sum to infinity of aritmetico-geometric series with }\\a = \frac{1}{n}, r = \frac{n-1}{n} \text{ and } d = \frac{1}{n} \right) \\= 1 + n - 1 = n$

Reference: https://en.wikipedia.org/wiki/Arithmetico-geometric_sequence

Or we can also do,

$E= 1 \times \frac{1}{n} + 2 \times \frac{n-1}{n^2}  + 3 \times \frac{ (n-1)^2}{n^3} + \dots $

$E \frac{n-1}{n}  = \frac{n-1}{n^2} + 2 \times \frac{(n-1)^2}{n^3} + 3 \times \frac{(n-1)^3}{n^4}  + \dots $

$  E  -E\frac{n-1}{n} =  \frac{1}{n} +   \frac{n-1}{n^2}  +   \frac{ (n-1)^2}{n^3} + \dots $

$E. \frac{1}{n} = \frac{(1/n)}{1 - \frac{n-1}{n}} = 1 \left( \text{Sum to infinity of GP with } a = \frac{1}{n} \text{ and } r = \frac{n-1}{n} \right) \\ \implies E = n$

Correct Answer: $A$

Comments

We did infinity sum because here we are choosing index randomly between i….n, there is no where mentioned that you will always choose distinct index ,you might have choosen any index multiple times,and thats why there can be infinite random indexes we can choose until the key is found.

@Arjun sir’s comment 

while(1)
{
    check a[i];
}

where i is any value from 1..n. Unless check succeeds, it never ends.

---

Arithmetico series ,it is not gp series ,it is combination of arithmetic and gp series.

---

@Arjun sir, With reference to AGP, as far as the formula to calculate the sum to infinity of arithmetic–geometric series is concerned, Shouldn’t the value of ‘a’ be = 1? and the value of ‘b’ = 1/n and the value of ‘d‘ be = 1?

As per the formula given in AGP, they assumed ‘a’ to be the first term of AP with a difference of ‘d’ and ‘b’ to be the first term of GP with a common ratio of ‘r’.

---

@Srestha No. It is because the other one is doing linear search whereas here the search algorithm is different; hence the probabilities also change.

And can we say like that because here the 'i' is chosen uniformly at "random" that's why the probabilities here are different with respect to this Question?.

Answer 2

 

Answer Option A

Answer 3

Why is the second term not , but ?

The way I see it, the probability of getting it in 2nd try is: Probability of failing at first trial times probability of succeeding in 2nd trial.

It's not like we are removing one element from the list after the first trial.

Here is my calculation and proof:

Answer 4

Let expected number of comparisons be E. Value of E is the sum of following expression for all the possible cases.

case: 1 

If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n

case: 2

If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n

case: 3

If A[i] is found in the third attempt 
  number of comparisons = 3
  probability of the case  = (n-1)/n*(n-1)/n*1/n

There are actually infinite such cases. So, we have following infinite series for E.

E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)

After multiplying equation (1) with (n-1)/n, we get

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Subtracting (2) from (1), we get

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

The expression on right side is a GP with infinite elements. Let us apply the sum formula (a/(1-r))

  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n

Comments

Till Case 3 it is clear but then Why multiply 2 in second term, 3 in third term..and so on while finding the infinite sum?

Edit: Never mind, I understood. :-)