When \(\textsc{Randomized-Quicksort}\) runs, how many calls are made to the random-number generator \(\textsc{Random}\) in the worst case? How about in the best case? Give your answer in terms of \(\Theta\)-notation.
The number of calls to \(\textsc{Random}\) equals the number of times \(\textsc{Randomized-Partition}\) is called, since each invocation of \(\textsc{Randomized-Partition}\) makes exactly one call to \(\textsc{Random}\) to select a pivot.
- Worst case: When partitions are maximally unbalanced (one side has \(n-1\) elements, the other has 0), the recursion creates a linear chain. We partition subarrays of sizes \(n\), \(n-1\), \(n-2\), …, down to 2. This gives us:
- Best case: When partitions are perfectly balanced, we have a complete binary recursion tree of depth \(\lg n\). The number of internal nodes (each representing a partition call) in a complete binary tree with \(n\) leaves is approximately \(n - 1\), which is \(\Theta(n)\).