In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an average case of quick sort, for lets say the partitions are always broken using the ration 1:9 or 1:4 every time.

How would you calculate the call stack depth in that case ?

Now most text books show the depth of the call stack as $\log_{split ratio} n$. I just don't know how that works.

Can someone explain the intuition behind that ? I mean how can you express something as the logarithm of a ratio if the tree is unbalanced ?

  • $\begingroup$ Read any moderately rigorous average-case analysis of Quicksort. Most algorithms textbooks contain one. (Note that "average case" in the literature usually refers to the random permutation model. I have never seen an analysis that would refer to an "average split ratio". Not sure if that would make even sense.) $\endgroup$ – Raphael Aug 18 '17 at 18:08
  • $\begingroup$ @Raphael Have a look at the edited question now. $\endgroup$ – ng.newbie Aug 18 '17 at 18:34
  • $\begingroup$ When you split a range in two parts, put the larger subrange on the stack. Then the worst case is the base two logarithm of n. The average case is better (as far as stack depth is concerned, but likely not otherwise). $\endgroup$ – gnasher729 Aug 18 '17 at 18:36
  • $\begingroup$ @gnasher729 No I want to know how the formula works. Its more of a mathematical question. If the list is partitioned using 1:4 ratio, then I just don't understand how the max depth is given by $\log_{1\4} n$ ? I mean I can understand it for when it is divided as 1:1, each depth is a power of 2. But for 1:4 the smaller side ends before the larger side so the divisions aren't exactly powers of 1/4. So does the logarithm give the right answer ? $\endgroup$ – ng.newbie Aug 18 '17 at 19:15
  • 1
    $\begingroup$ Hint: Fix a cost measure. Set up a recurrence for it. Solve. $\endgroup$ – Raphael Aug 18 '17 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.