Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 5

Problem:

Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case --- equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the minimum-possible and maximum-possible recursion depth of QuickSort, respectively?

Solution:

The minimum possible depth occurs when we pick median all the time, and the minimum depth would be $\lg n = \theta(\log n)$.

The maximu mpossible depth occurs when we pick the smallest element all the time, and the maximum depth would be $n = \theta(n)$.