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.