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?

For a randomized algorithm, it is highly probable to produce the expected running time, but little probability to produce worst-case running time. For randomized version of quicksort, the probability to produce worst-case running time is:

$$ \begin{aligned} \frac{2^{n}}{n!}\cr \end{aligned} $$

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 worst case, RANDOM will always select the minimum or maximum number, each element will be selected as pivot. The number of calls to RANDOM is: $\Theta(n)$.

In best cast, let $F(n)$ be the calls made to RAMDOM, $G(n) = \min(F(n))$

$$ \begin{align} F(1) = 0\cr F(2) = 1\cr G(3) = 1\cr G(n) = \min(G(k)+G(n-k-1)+1)\cr G(n) = 2G((n-1)/2) +1(\text{I guess})\cr G(n) = O(n)\cr \end{align} $$