

7.3 A randomized version of quicksort

7.3-1

Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?

We may be interested in the worst-case performance, but in that case, the randomization is irrelevant: it won't improve the worst case. What randomization can do is make the chance of encountering a worst-case scenario small.

7.3-2

When $\text{RANDOMIZED-QUICKSORT}$ runs, how many calls are made to the random number generator $\text{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 $\text{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.