[Algo] Exercise 7.3

Exercise 7.3-1
Why do we analyze the average-case performance of a randomized algorithm and not its worst-case performance?
Solution:
Randomized algorithm will not improve the worst case. What randomization can do is make the chance of encountering a worst-case scenario small.


Exercise 7.3-2
During the running time of the procedure RANDOMIZED-QUICKSORT, how many calls are made to the random-number generator RANDOM in the worst case? How about in the best case case? Give your answer in terms of $\Theta$-notation.
Solution:
There are $\Theta(n)$ calls to RANDOM in the worst case. There are also $\Theta(n)$ calls to RANDOM in the best case. Because each call to RANDOM chooses a pivot, and after this call the pivot will not participate in further partition. There are n items in the list, and there will be at most n call to RANDOM.