The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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}$
asked in Algorithms by Veteran (59.8k points)
recategorized by | 5.2k views

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


For a list with n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

If the value being sought occurs k times in the list, and all orderings of the list are equally likely, the expected number of comparisons is

{\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac  {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}

For example, if the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is

 {\frac  {n+1}2}.

However, if it is known that it occurs once, then at most n - 1 comparisons are needed, and the expected number of comparisons is

\displaystyle {\frac  {(n+2)(n-1)}{2n}}

(for example, for n = 2 this is 1, corresponding to a single if-then-else construct).

$ E(X) = \dfrac{1}{n} + \dfrac{n-1}{n}(E(X) + 1) = n, \frac{1}{n} \text{ for success and repeat on failure.}$

Geometric distribution ....

7 Answers

+52 votes
Best answer

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$


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 (396k points)
edited by
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.

Actually I think here search is linear but not sequential

That is why Arithmetico geometric series used.

And then simply put in formula



@srestha @arjun sir

probability is assigned to each iteration

SO prob of second iteration is (n-1) / n got it...

but how prob of 3rd iteration is (n-1)2 / n
chk from wiki link given in answer and try to analyze :)


Probability that there will be 3 comparisons =

P(1st attempt fail) * P(2nd attempt fail)*P(3rd attempt success)

=$(n-1)/n$   * $(n-1)/n$   * $(1/n)$

= ${(n-1)^2/n^3}$

   // always we choose from n items so total cases n in denominator and for numerator  in case of failure it can return any one from n-1 items but not the item that we need ,however for success it will return only the item we need.I hope you get it now!!!!


thanku so much :)

canyou also explain how it is expanded using the arithometric formula to get n

what is the formula used
Multiply the equation in the answer say 1 with the common ratio and get a new equation say 2.

Now subtract 1-2.Try to solve you will get
arjun sir what a capacity of logic u have
Why is it so arjun sir that in gate 96 problem we are considering the probabilities assisn to each slots but here we are considering the probabilities regarding for the itterations...
+12 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:


answered by Boss (22.2k points)
+7 votes

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


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
answered by Junior (913 points)
edited by
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. :-)
+6 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

Hence answer is   a) n .

answered by Boss (11.7k points)
@Arjun sir please say are the both qsns talking about same thing ?
I guess yes..
+5 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.


answered by Active (2k points)
+3 votes


Answer Option A

answered by Junior (659 points)
edited by
0 votes
All are busy giving proof for this answer let me share what I thought

Now Remember Hashing in that there is concept called open addressing now whether u take linear probe or quadratic probe the no of probe sequence generated are n hence in worst n comparison will be needed and that will be the answer.

I have taken hashing because it is most popular DS for searching

@Arjun Sir plz verify if am thinking In  a right manner
answered by (365 points)

Related questions

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
50,115 questions
53,224 answers
70,473 users