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) $.
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) $.
No comments:
Post a Comment