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?

Define the recursion depth of quicksort to be the maximum number of su

1.	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?
Answer» 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) $...