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

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

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

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.

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

random number is calculated by a predefined formula .