Question

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 1

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

..

Answer 2

Answer:

Explanation:

Given - The recursion depth of quicksort to be the maximum number of successive recursive calls before it hits the base

To Find  - Minimum-possible and maximum-possible recursion depth of quicksort .

When we pick median all the time, we get the least depth, which is $ lg n = theta(log n) $.

The maximum depth is reached when we always choose the smallest element, and the maximum depth is $ n = theta(n) $.