Suppose that the splits at every level of Quicksort are in proportion 1-β to β, where 0<β≤0.5 is a constant. The number of elements in an array is n. The maximum depth is approximately
A. 0.5 β Ig n
B. 0.5 (1–β) Ig n
C. – (Ig n)/(Ig β)
D. – (Ig n)/Ig (1–β)
Answer:D
Suppose that the splits at every level of Quicksort are in proportion 1-β to β, where 0<β≤0.5 is a constant. The number of elements in an array is n. The maximum depth is approximately
A. 0.5 β Ig n B. 0.5 (1–β) Ig n C. – (Ig n)/(Ig β) D. – (Ig n)/Ig (1–β)