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

Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values:

- Choose an $i$ at random from $1..n$
- 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?

- $n$
- $n-1$
- $2n$
- $\frac{n}{2}$

### 6 Comments

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

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

.

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

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

## 8 Answers

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$

### 21 Comments

@Arjun Sir

why here u used Arithmetico-geometric_sequence

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

here in this question asking about expected number of comparisons

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

is that making difference?

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?

@ A_i_$_h

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!!!!

Those who did not understood @Arjun sir’s comment .

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.

Read the question you will find Goto1 at the 2^{nd} step this is like a loop here it means that if you don’t find the key in 1^{st} iteration then start over search again,and this goes until it is found. That’s why if you don’t found the key in 1^{st} attempt then in second attempt your probability will be

second attempt probability= probability of failure in first attempt * probability of success in second attempt(if in case we found it in 2 comparisons)

second attempt probability= (1-1/n) * (1/n) = (n-1/n)*1/n = n-1/n^2.

hope this helps:) this was my doubt also.

We did infinity sum because here we are choosing index randomly between i….n, there is no where mentioned that you will always choose distinct index ,you might have choosen any index multiple times,and thats why there can be infinite random indexes we can choose until the key is found.

@Arjun sir’s comment

while(1) { check a[i]; }where i is any value from 1..n. Unless check succeeds, it never ends.

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

**case: ****1 **

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

### 1 comment

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

https://gateoverflow.in/3561/gate2006-it-22

Hence answer is a) 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.

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