1.7k 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}$

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$

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$

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

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?

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:

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

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.

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 .

@Arjun sir please say are the both qsns talking about same thing ?
I guess yes..