GATE CSE
First time here? Checkout the FAQ!
x
+17 votes
2k 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 Algorithms by Veteran (66.2k points) 1157 2199 2523
recategorized by | 2k views

Notice --> Observe @Arjun sir's answer. Here we will take sum of infinite series. Reason is also mentioned in comment section. 

5 Answers

+30 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 (319k points) 580 1448 2962
selected by
All three links provided by you are same.. @sushmita
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?

same doubt sretha
@srestha for both questions it is probability only. But here search is not "sequential" and so we cannot evaluate the comparisons based on probabilities assigned to each location. Instead we assign probabilities for each iteration.
+11 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.8k points) 21 64 140
+4 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 = 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.3k points) 1 6 20
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.6k points) 3 9 19
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 by Boss (7k points) 4 13 42
@Arjun sir please say are the both qsns talking about same thing ?
I guess yes..


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23438 Points

  2. Bikram

    17108 Points

  3. Habibkhan

    8344 Points

  4. srestha

    6314 Points

  5. Debashish Deka

    5458 Points

  6. jothee

    5008 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4390 Points

  9. sushmita

    3996 Points

  10. Rishi yadav

    3838 Points


Recent Badges

Popular Question sunil sarode
Verified Human nandisrinivas
Nice Question shraddha priya
Popular Question just_bhavana
Famous Question rahul sharma 5
Popular Question Jithin Jayan
Great Answer Sankaranarayanan P.N
Good Question jothee
Great Answer Sankaranarayanan P.N
Famous Question pC
27,346 questions
35,200 answers
84,228 comments
33,327 users