The Gateway to Computer Science Excellence
0 votes
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}$
in Algorithms by Boss (30.2k points)
recategorized by | 620 views

1 Answer

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


 

by (283 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,698 users