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.

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.

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