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?
Expected number of indexes to be analyzed should be n, if x appears just once in the array.
ReplyDelete