Exercise 7.3.2

When RANDOMIZED-QUICKSORT runs, how many calls are made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$-notation.

In the worst case, the number of calls to RANDOM is:

$$ T(n) = T(n-1) + 1 = n = \Theta(n) $$

As for the best case:

$$ T(n) = 2T(n/2) + 1 = \Theta(n) $$

This is not too surprising, because each third element (at least) gets picked as pivot.