The Gateway to Computer Science Excellence

0 votes

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

- $-\frac{lgn}{lg(1-\alpha)}$
- $-\frac{lg(1-\alpha)}{lgn}$
- $-\frac{lgn}{lg\alpha}$
- $-\frac{lg\alpha}{lgn}$

+1 vote

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-α)

52,314 questions

60,435 answers

201,773 comments

95,251 users