Introduction
Running Time
Choosing the pivot randomly is known to be the best way of performing quick sort because on an average it achieves a run time of nlogn.
QuestionDefine the recursion depth of QuickSort to be the maximum no. of successive recursive calls before it hits the base case [Note: 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?
Ans
Best Case: When the algorithm always picks the median as a pivot, in which case the recursion is essentially identical to that in MergeSort - Θ(log(n)).
Worst Case: The min or the max is always chosen as the pivot, resulting in linear depth - Θ(n)
Source Code
