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 analyze the expected run time because it represents the more typical time cost. Also, we are doing the expected run time over the possible randomness used during computation because it can't be produced adversarially, unlike when doing expected run time over all possible inputs to the algorithm.

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.