Thursday, April 8, 2010

Random search in a random array, with duplicates

I already put this problem, but now assume that there are k elements with value x. What is the expected running time?

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.

1 comment:

  1. In this case the expected running time should be n/k