Consider the following algorithm for searching for a given number…

0

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

Ravi Garg edited question
    0
    Ashutosh Bhatia (anonymous)

    The number of comparisons required to search an element x in array a is a geometric random variable with success probability 1/n, Therefore the expected number of comparisons required is 1/(1/n) = n

    Ashutosh Bhatia answered
      Add image to editor add image from link

      Question stats

      • Active
      • Views199 times
      • Answers1 answer
      • Followers1 follower
      Question and answer is powered by AnsPress