Suppose that the splits at every level of quicksort are in the proportion…
2014
Suppose that the splits at every level of quicksort are in the proportion (1–𝛼) to 𝛼, where \(0 < 𝛼 ≤ \frac 1 2\) is a constant. The minimum depth of a leaf in the recursion tree is approximately given by
- A.
\(-\frac{lgn}{lg(1-\alpha)}\) - B.
\(-\frac{lg(1-\alpha)}{lgn}\) - C.
\(-\frac{lgn}{lg\alpha}\) - D.
\(-\frac{lg\alpha}{lgn}\)
Attempted by 186 students.
Show answer & explanation
Correct answer: A
Answer: −lg n / lg(1−α)
Derivation:
At depth k, repeatedly following the larger partition of size (1−α) yields a subproblem of size n(1−α)^k.
A leaf occurs when the subproblem size is about 1, so set n(1−α)^k ≈ 1, i.e. (1−α)^k = 1/n.
Solve for k: k = log_{1−α}(1/n) = − lg n / lg(1−α).
Since 0 < α ≤ 1/2, 1−α < 1 and lg(1−α) < 0, making the quotient positive as required.
Note: The expression −lg n / lg α would give the maximum (deepest) leaf depth obtained by always following the smaller α partition; the minimum depth uses the larger (1−α) partition as shown above.