Suppose that the splits at every level of quicksort are in the proportion \(1-\alpha\) to \(\alpha\), where \(0 < \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.)
When partitions split in a constant proportion \(1-\alpha\) to \(\alpha\) at every level, the recursion tree becomes unbalanced, with one branch shrinking faster than the other (assuming \(\alpha \ne 1/2\)). The depths of the shortest and longest paths to leaves can be determined by analyzing how quickly each branch reduces to size 1.
Minimum Depth
The shortest path follows the branch that shrinks fastest, which is the smaller side of each partition. Since \(\alpha \leq 1/2\), the \(\alpha\) fraction is the smaller one (or equal when \(\alpha = 1/2\)).
At each level going down this path, the problem size multiplies by \(\alpha\):
- Level 0: size \(n\)
- Level 1: size \(\alpha n\)
- Level 2: size \(\alpha^2 n\)
- Level \(d\): size \(\alpha^d n\)
The recursion reaches a leaf when the problem size becomes 1:
\[\alpha^d n = 1\]Solving for \(d\):
\[\begin{align*} \alpha^d &= \frac{1}{n} \\ d \lg \alpha &= \lg(1/n) = -\lg n \\ d &= -\frac{\lg n}{\lg \alpha} \end{align*}\]Since \(0 < \alpha < 1\), we have \(\lg \alpha < 0\), making this expression positive.
Maximum Depth
The longest path follows the branch that shrinks slowest, which is the larger side with fraction \(1-\alpha\).
At each level going down this path, the problem size multiplies by \(1-\alpha\):
- Level \(d\): size \((1-\alpha)^d n\)
The recursion reaches a leaf when:
\[(1-\alpha)^d n = 1\]Solving for \(d\):
\[\begin{align*} (1-\alpha)^d &= \frac{1}{n} \\ d \lg(1-\alpha) &= -\lg n \\ d &= -\frac{\lg n}{\lg(1-\alpha)} \end{align*}\]Again, since \(0 < 1-\alpha < 1\) (because \(\alpha > 0\)), we have \(\lg(1-\alpha) < 0\).
Both depths are \(\Theta(\lg n)\), which means even with unbalanced partitions, the tree depth remains logarithmic as long as the split ratio is constant. For example:
- When \(\alpha = 1/10\) (a 9-to-1 split):
- Minimum depth \(\approx -\lg n / \lg(0.1) \approx 0.301 \lg n\)
- Maximum depth \(\approx -\lg n / \lg(0.9) \approx 6.579 \lg n\)
The tree is unbalanced, but both paths are still \(O(\lg n)\).