GATE CSE
First time here? Checkout the FAQ!
x
+11 votes
1.4k views

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?

  1. $n$
  2. $n-1$
  3. $2n$
  4. $\frac{n}{2}$
asked in Probability by Veteran (59.2k points)   | 1.4k views

5 Answers

+24 votes
Best answer

Expected number of comparisons (E) = 1 * Probability of find on first comparison + 2 * Probability of find on second comparison + ... + i* 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$

Ref: 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$

 

answered by Veteran (286k points)  
selected by
yes, even there is a doubt why algorithmico-geometric series require here?

@Arjun Sir

why here u used Arithmetico-geometric_sequence

and in http://gateoverflow.in/2742/gate1996-2-13-isro2016-28 u just used probability

here in this question asking about expected number of comparisons

and  in http://gateoverflow.in/2742/gate1996-2-13-isro2016-28 question asking about average number of key comparisons

is that making difference?

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

ok

then what this line exactly mean?

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

1 is here picking the element in 1st attempt and 1/n is we are with only one comparison we are getting the element. rt?

then , $2 \times \frac{n-1}{n^2}$ is picking the element in 2nd attempt and $\frac{n-1}{n^2}$ means with 1/n and (n-1)/n comparison we need to do this? why so?means every time we need to do one comparison first and then (n-1) all comparison next? not clear this part. Could u plz explain?

+9 votes

Why is the third term 2 \times \frac{n-1}{n} \times \frac{1}{n-1}, and not 2 \times \frac{n-1}{n} \times \frac{1}{n}

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:

image

answered by Veteran (19.3k points)  
+1 vote

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

case: 

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 = 2
  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
answered by Active (1.1k points)  
0 votes

This is a type of geometric distribution. Searching an element randomly in array is like tossing a coin(not necessarily fair) until first head comes. Probability of which is 1/n. I am assuming that element is actually in an array. Expected value of geometric random variable is 1/p where p is the probability of success, here 1/n. So answer is 1/(1/n) = n.

Ref. https://en.wikipedia.org/wiki/Geometric_distribution

answered by Active (1.1k points)  
0 votes

Do not know if it is a correct approach. Some one please verify.
Suppose array contains 10 elements.
'i' will be chosen at random, so probability that we will get our element in first try = 1/10.
Expected number of try for getting the element is  1/p  =   10
http://gateoverflow.in/3561/gate2006-it-22

Hence answer is   a) n .

answered ago by Loyal (2.5k points)  


Top Users Jun 2017
  1. Bikram

    3694 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1372 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1114 Points

  8. Arjun

    930 Points

  9. srestha

    922 Points

  10. Debashish Deka

    896 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1950 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,353 questions
30,061 answers
67,357 comments
28,378 users