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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

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

0

+1

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).

+40 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 i^{th} 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$

+1

@Srestha No. It is because the other one is doing linear search whereas here the search algorithm is different; hence the probabilities also change.

0

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?

+1

@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.

0

@sushmita

Actually I think here search is linear but not sequential

That is why Arithmetico geometric series used.

And then simply put in formula

t1=ab

t2=(a+d)br

.....................

Actually I think here search is linear but not sequential

That is why Arithmetico geometric series used.

And then simply put in formula

t1=ab

t2=(a+d)br

.....................

0

@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

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

+1

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

+12 votes

Why is the third term , and not

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:

+6 votes

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

+3 votes

+3 votes

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 .

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,943 questions

41,958 answers

119,194 comments

41,472 users