##### what is the expected number of comparisons made by the algorithm?

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 uniformaly 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 ?

option

1- n

2- n-1

3- 2n

4- n/2

Niket Gangwar
19 Aug 2017 02:39 am

We will like to first find the probability of success.

Since given random but uniformly , therefore probability of getting a number = 1/n .

So probability of success can be calculated as if found in 1st comparison,if not in 1st then in 2nd,if not in 1st and 2nd then in third and so on.

P(S)= 1/n + (1-1/n)*1/n +(1-1/n)(1-1/n)(1/n) +_ _  _  _  _

or p(S)= 1/n + (n-1)/n^2 + (n-1)^2/n^3 +  _  _  _  _  _  _  _

this is infinite G.P with a = 1/n and r = (n-1)/n

p(s)=(1/n)/1-(n-1)/n=1/n

So, no. of times we have to try for success = 1/p(s)= n

Therefore, 'n' number of comparisons.

Rahul
19 Aug 2017 09:55 am

My brother they ask us to find expected value not probablity

expectation equal to (probability)* random variable.