GATE CSE 2002 | Question: 2.10

Question

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?

• A. $n$
• B. $n-1$
• C. $2n$
• D. $\frac{n}{2}$

Comments

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

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

https://en.wikipedia.org/wiki/Linear_search

---

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

---

Hi can u tell why e+1 is multiplied on failure

---

https://gateoverflow.in/840/gate2002-2-10?start=5

---

Let X be the expected no. of comparisons.
X=(Probability of success)*1 + (Probability of Failure)*(X+1)
X=(1/n)*1 + ((n-1)/n)*(X+1)
After solving this, X=n

---

if element is in the array probality of choosing i'th index such that a[i]=x;-----> 1/n

and probablity of index such that element is not in the array. ------------> (n-1)/n

now expected no . of comparison  E[C] = probality of succes * cost    +      prbality of failure * cost

E[C] = 1/n  * [# of compr. if i'th indext is our index] +  (n-1)/n *  [n-1 comparison if element not in the array]

E[C] = 1/n * 1 + (n-1)/n *  (n-1)... uppon solving it gives n

---

Let there be 4 numbers : x,y,z and w

All outcomes possibilities is 1/4

Now let's say we want to search for x

What can be expected value?

Hence expectation is "n"

---

Answer :(A)

---

Option : - A

 

---

Ans: n

Answer 1

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).(1/n)} {1 - \frac{n-1}{n} } + \frac{(1).(1/n)((n-1)/n)}{\left( {1- \frac{n-1}{n} }\right)^2} \\ \left( \text{Sum to infinity of aritmetico-geometric series with }\\a = d = 1, r = \frac{n-1}{n} \text{ and } b = \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$

Comments

@srestha mam how u r getting these many doubts in almost every question ?

Those who have great enthusiasm to learn the subject can only get these many doubt. 

I am learning something from your doubts and clarifications posted by others.

Thank you so much 

---

Amazing Solution. Thank you very much!

---

Damn. I am here again after an year. Damn. Dont know if i should feel sad that i am dropping or nostalgic xd. Nevermind. Moving onto the next question.

Answer 2

 

Answer Option A

Comments

Should be the best answer

---

Undoubtedly the best answer for this question!

Answer 3

Why is the second term not , but ?

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:

Comments

Because we are not deleting anything, the probability of finding an element on any try will be 1/n, the program doesn't remember if it failed to find the element on a certain index

Answer 4

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 .

Comments

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

---

Yes. That question will be correlated to this question.

---

@Shaik Masthan

I am not able to understand Ahwan's  approach. Can you please explain.

---

This question can be correlated with tossing a coin until a Head appear due to every trail is independent and sucess rate is not changed.

In the tossing a coin for head, sucess probability =$\frac{1}{2}$

In this question, sucess probability =$\frac{1}{n}$

Expected number of comparissions for a sucess probability with $\frac{1}{n}$ and independent trails= n.

Answer 5

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

Comments

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

---

But I didn't, could you tell why we are multiplying

Answer 6

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