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

We will like to first find the probability of success.

Since given random but

therefore probability of getting a number = 1/n .uniformly ,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.

My brother they ask us to find expected value not probablity

expectation equal to (probability)* random variable.