Maximum and minimum sorting depth

Question

This was a CLR (Introduction to Algorithms) issue. The question goes as follows:

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

I do not understand how to reach this solution. by reference, they show that with a ratio of 1: 9, the maximum depth is log n / log (10/9) and the minimum log n / log (10). Then how to prove the above formula. Please help me where I am going wrong, as I am new to the Algorithms and Data Structures course.

Answer 1

First, consider this simple task. Suppose you have a number n and a fraction (from 0 to 1) p. How many times do you need to multiply n by p so that the total 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 consider your problem. Suppose you send the shorter of the two segments to the left child and longer to the desired child. For the leftmost chain, the length is specified by replacing \ alpha as p in the above equation. For the right chain, the length is calculated by substituting 1- \ alpha as p. That is why you have these numbers as answers.