Consider the following randomized algorithm for searching an array for a particular value. Suppose we have an integer array A of length n and we wish to find the value x in A. Pick a random index i into A. If A[i] == x, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that A[j] = x or until we have searched every element of A. For efficiency, no array element should be visited more than once.

a.Write an algorithm RANDOMIZED_SEARCH that performs the random search described above. Your algorithm must use O(1) space, but is free to rearrange the order of elements within an array (i.e., side-effects are allowed).

b.Determine the best-case, worst-case, and average case runtime of the algorithm assuming all of the values in A are distinct. The value x may or may not exist in the array. You may assume that each search iteration has cost 1.

c.Suppose now that for any index i, the probability that A[i] = x is given by p, i.e.

P(A[i] = x) = p). Derive an expression (leaving it as a summation is OK) for the

expected value of the run-time of this algorithm. Again, you may assume that each search iteration has cost 1. Please do not forget to consider the case that x does not occur at all in the array.