Given below is a randomized algorithm for searching for a value x in an unsorted array consisting of n elements. The strategy it utilizes is as follows. It randomly picks an index i between 1 and n (inclusive). If A[i] = x, it terminates. Otherwise, it continues picking random indices until it finds an index j such that A[j] = x, or it has checked every element of A. Note that it may examine a given element more than once. Give the average-case running time both in terms of T(n) and O() for this algorithm. Clearly explain how you arrived at your answer. Assume we are using 1-based indexing for the array.

Hint: Look up information about simple probability experiments, maybe a particular kind of distribution that begins with a B

search(x, A):

n = A.length();

checked = { };

found = false;

while ((! found) && (checked.size() != n)) do // assume checked.size() takes O(1) time

{

i = RANDOM(1, n); if (A[i] == x) found = true; else checked = checked U i; // assume this can be done in O(1) time

}

return(found);