RANDOMIZED-QUICKSORTruns, how many calls are made to the random number generator
RANDOMin 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
$$ 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.