GATE CS 2002 Q2.10 — Searching, Sorting, Hashing

The algorithm describes a randomized search with replacement. Let's analyze the probability of finding the element $x$ in each step:

• Since the array $A[1..n]$ has $n$ distinct elements and $x$ is guaranteed to be present, there is exactly one index $i$ such that $A[i] = x$.
• In each step, an index $i$ is chosen uniformly at random from the set of indices.
• The probability of success (finding $x$) in any single trial is:
  $$p = \frac{1}{n}$$
• The probability of failure in any single trial is:
  $$q = 1 - p = 1 - \frac{1}{n}$$

Since the choices in each step are independent, the number of trials $N$ required to find $x$ follows a Geometric distribution with success probability $p = \frac{1}{n}$.

The expected number of trials (which is equal to the expected number of comparisons, as each trial makes exactly one comparison) is given by the expectation of a geometric random variable:

Thus, the expected number of comparisons made by the algorithm before it terminates is $n$.

Correct Option: A