Consider the following algorithm for searching for a given number x in an…
2002
Consider the following algorithm for searching for a given number x in an unsorted array A[1...n] having n distinct values: choose i uniformly at random from 1...n; if A[i] = x, stop; otherwise repeat. Assuming x is present in A, what is the expected number of comparisons made before the algorithm terminates?
- A.
n
- B.
n - 1
- C.
2n
- D.
n/2
Attempted by 59 students.
Show answer & explanation
Correct answer: A
Since A has n distinct values and x is present, exactly one index contains x. On each iteration, the algorithm chooses one of the n indices uniformly at random, so the probability of success in a comparison is 1/n. The number of comparisons until the first success follows a geometric distribution with mean 1/p. Here p = 1/n, so the expected number of comparisons is 1/(1/n) = n.