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)$.