reopened by
22,014 views
71 votes
71 votes

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}$
reopened by

11 Answers

Best answer
106 votes
106 votes

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$

edited by
17 votes
17 votes

Why is the second term not 2 \times \frac{n-1}{n} \times \frac{1}{n-1}, but 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

8 votes
8 votes

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 = 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
edited by
Answer:

Related questions

47 votes
47 votes
7 answers
2
Kathleen asked Sep 15, 2014
17,728 views
The running time of the following algorithmProcedure $A(n)$If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$;is best described by$O(n)$$O(\log ...
35 votes
35 votes
2 answers
4
Kathleen asked Sep 15, 2014
11,773 views
The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is$2^k$$\frac{(3^{k+1}-1)}{2}$$3^{\log_2 k}$$2^{\log_3 k}$