620 views

Suppose that the splits at every level of quicksort are in the proportion $(1 – \alpha)$ to $\alpha$, where $0<\alpha\leq\frac{1}{2}$ is a constant. The minimum depth of a leaf in the recursion tree is approximately given by

1. $-\frac{lgn}{lg(1-\alpha)}$
2. $-\frac{lg(1-\alpha)}{lgn}$
3. $-\frac{lgn}{lg\alpha}$
4. $-\frac{lg\alpha}{lgn}$

recategorized | 620 views

if we split with α, we will get minimum depth. suppose α=1/2 means pivot is the middle element. with such case recursion tree will be with minimum depth. other cases it will have maximum.

1. nα^k=1
k=-logn/log
α

2. n(1-α)^k=1
k=-logn/log(1-
α)

by (283 points)