Consider the following algorithm for searching for a given number x in an unsorted array A[l. .n] having n distinct values:

1. Choose an i uniformly at random from I. .nl

2. If A[i]=x then Stop else Goto 1;

Assuming that x is present A, what is the expected number of comparisons made by the

algorithm before it terminates?

(a) n

(b) n – 1

(c) 2n

(d)n/2

### Question stats

Question and answer is powered by AnsPress