recategorized by
1,988 views
0 votes
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

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

2 Answers

2 votes
2 votes

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


 

Answer:

Related questions

0 votes
0 votes
2 answers
2
1 votes
1 votes
1 answer
3
makhdoom ghaya asked Jul 10, 2016
4,510 views
The reverse polish notation equivalent to the infix expression $((A + B) ^{*} C + D)/(E + F + G)$$A B + C ^{*} D + EF + G + /$ $A B + C D ^{*} + E F + G + /$ $A B + C ^{*...
1 votes
1 votes
1 answer
4
makhdoom ghaya asked Jul 11, 2016
2,510 views
The solution of the recurrence relation of $ T(n)=3T\left(floor \left(\frac{n}{4}\right)\right)+n$ is$O(n^{2})$$O(n/g n)$$O(n)$ $O(l g n)$