Sunday, March 14, 2010

Random search in random array

Suppose you have an array of random integers A[i] i = 0, ... , n-1. Suppose you adopt the following random search strategy for value x. Pick a random index i into A. If A[i] = x, then we terminate; otherwise, continue the search by picking a new random index into A. Note that we may examine a given element more than once.

What is the expected number of indexes analyzed?

1 comment:

  1. Expected number of indexes to be analyzed should be n, if x appears just once in the array.