7.3 A randomized version of quicksort

7.3-1

The worst-case is a special case, analyzing the expected running time can be more resonable that reflects the complexity of the algorithm.

7.3-2

The worst-case satifies $T(n) = T(n - 1) + \Theta(1)$, thus $T(n) = \Theta(n)$. The best case satifies $T(n) = 2T(\frac{n}{2}) + \Theta(1)$, thus $T(n) = \Theta(n)$.