Maximum and minimum depth of quicksort

Question

This was a problem of CLR (Introduction to Algorithms) The question goes as follow:

Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)http://integrator-crimea.com/ddu0043.html

I'm not getting how to reach this solution. as per the link they show that for a ratio of 1:9 the max depth is log n/log(10/9) and minimum log n/log(10). Then how can the above formula be proved. Please help me as to where am I going wrong as I'm new to Algorithms and Data Structures course.

Answer 1

First, let us consider this simple problem. Assume you a number n and a fraction (between 0 and 1) p. How many times do you need to multiply n with p so that resulting number is less than or equal to 1?

n*p^k <= 1
log(n)+k*log(p) <= 0
log(n) <= -k*log(p)
k => -log(n)/log(p)

Now, let us consider your problem. Assume you send the shorter of the two segments to the left child and longer to the right child. For the left-most chain, the length is given by substituting \alpha as p in the above equation. For the right most chain, the length is calculated by substituting 1-\alpha as p. Which is why you have those numbers as answers.

Answer 2

general question and the answer

Suppose that the splits at every level of quicksort are in proportion 1−α to α, where 0< α ≤1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately −lgn/lgα and the maximum depth is approximately −lgn/lg(1−α). (Don't worry about integer round-off.)

answer :

The minimum depth follows a path that always takes the smaller part of the partition i.e., that multiplies the number of elements by α. One iteration reduces the number of elements from n to αn, and i iterations reduce the number of elements to (α^i)n. At a leaf, there is just one remaining element, and so at a minimum-depth leaf of depth m, we have (α^m)n=1. Thus, αm=1/n. Taking logs, we get m*lgα=−lgn, or m=−lgn/lgα. Similarly, maximum depth corresponds to always taking the larger part of the partition, i.e., keeping a fraction 1−α of the elements each time. The maximum depth M is reached when there is one element left, that is, when [(1−α)^M ]n=1. Thus, M=−lgn/lg(1−α).

All these equations are approximate because we are ignoring floors and ceilings.

source