##### Algorithm for searching

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?

1. n
2. n−1
3. 2n
4. n2
shivani
15 Oct 2017 07:57 pm
n , consider in worst case , it might be the case last random index is the correct index.
Gaurav Mohla
15 Oct 2017 08:13 pm

I am tending towards n but how can we be sure that the same random index is not again picked?

shivani
15 Oct 2017 10:52 pm

you can use some random number generator in which there is no repetition of numbers more appropriately some formulae to calculate random index,
like i= (i-2)%5678 something like this.

Gaurav Mohla
16 Oct 2017 12:27 am

its not given in the question. how can I be sure. This could go in an infinite loop

shivani
16 Oct 2017 10:57 am

random number is calculated by a predefined formula .