cormen 7.2 -5

Question

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).

how to procede with this problem i had seen stackoverflow solution but couldn’t understand 

https://stackoverflow.com/questions/17684680/maximum-and-minimum-depth-of-quicksort

Comments

@abhishekmehta4u @Mk Utkarsh

Answer 1

The size of the array is $n$.

Applying $quick\,sort$

In the first step, the array splits into sizes : $n*\alpha$ and $n*(1-\alpha)$

as $0\leq\alpha\leq\frac{1}{2}$ so $n*(1-\alpha)$ is the greater part of array.

In the second step $n*\alpha$ will split into $n*\alpha^{2}$,  $n*\alpha*(1-\alpha)$ and $n*(1-\alpha)$ into $n*(1-\alpha)*\alpha$, $n*(1-\alpha)^2$

The maximum time to traverse $i.e.$ the $maximum\,depth$ will be when we keep taking the maximum part $i.e.$
$n*(1-\alpha)\rightarrow n*(1-\alpha)^2\rightarrow n*(1-\alpha)^3\rightarrow .....\rightarrow n*(1-\alpha)^k$

$n*(1-\alpha)^k=1, $taking $log$ both sides

$log(n)+k*log(1-\alpha)=0$

$k=\frac{-log(n)}{log(1-\alpha)}=maximum\,depth$

The minimum depth will be when we traverse through sizes
$n*\alpha \rightarrow n*\alpha^{2}\rightarrow ..... \rightarrow n*\alpha^k$

$n*\alpha ^k=1,$ taking $log$ both sides

$log(n)+k*log(\alpha)=0$

$k=\frac{-log(n)}{log(\alpha)}=minimum\,depth$

Comments

nice explaination !!!!