7.2-5

Suppose that the splits at every level of quicksort are in the proportion $1- \alpha$ where $0 \leq \alpha \leq 1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $- lg n/lg \alpha$ and the maximum depth is approximately $- lg n/ lg (1 - \alpha)$ (Don’t worry about integer round-off.) The key is understand where do we get maximum and minimum depths in a tree. Since $\alpha$ is less than or equal to 0.5. If $\alpha \lt 0.5 $ the tree with $\alpha$ elements as the parent will end soon compared to $1-\alpha$ elements because it will less no of elements compared to $1-\alpha$. n is The tree with $\alpha n $ is reduced to $\alpha^2 n$ elements for second level. Similarly at k'th level it will be $\alpha ^ k n$. If the k level is a leaf then $$\alpha ^ k n = 1 $$ applying logarithm on both sides $$ log (\alpha ^ k n) = log 1 $$ $$ log (\alpha ^ k) = log 1 - log n $$ $$ k log (\alpha) = - log n $$ $$ k = - log n/log (\alpha) $$ Similarly the tree with (1-\alpha)n elements will have maximum depth. $$ (1-\alpha)^k = 1$$ applying logarithm on both sides $$ log (1-\alpha)^ k = log 1 - log n $$ $$ k = - log n/log (1-\alpha) $$