Multiple choice

Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from 1....n 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?

  1. n

  2. n -1

  3. 2n
  4. $\dfrac{n}{2}$
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Given array A[1.....n], an element A[i] is chosen randomly from 1 to n.This would require n selections & comparisons to find x in array

Keep practicing — related questions