Consider the following algorithm for searching for a given number x in an…
PYQ GATE 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 609 students.
Sign up free to check your answer
Sign up freeLoading lesson…