Suppose that the splits at every level of quicksort are in the proportion (1 − α) to α, where 0 < α ≤ 1/2 is a constant. The minimum depth of a leaf in the…

Explanation

In Quicksort, the depth of a leaf depends on how the input size reduces at each level. If the split is always in the ratio (1 − α) to α, the minimum depth corresponds to the path where the recursion always follows the smaller partition, i.e. of size αn. At each level the size becomes n, αn, α²n, α³n, … We stop when the size becomes 1: αᵏn = 1 ⇒ k log α + log n = 0 ⇒ k = −lg n / lg α. Hence the answer is (c).