UGC NET CSE | September 2013 | Part 2 | Question: 10

Question

Suppose that the splits at every level of Quicksort are in proportion $1-\beta \text{ to } \beta$, where $0 < \beta \leq 0.5$ is a constant. The number of elements in an array is n. The maximum depth is approximately

• A. 0.5 $\beta$ Ig n
• B. 0.5 (1-$\beta$) Ig n
• C. -(Ig n)/(Ig $\beta$)
• D. -(Ig n)/Ig (1-$\beta$)

Comments

There is a error in this question. It’s actually asking about the maximum depth of the leaf in the recursive tree. not the depth of the tree.

Max Depth of the leaf in the recursive tree is -

So, let’s suppose n is the number of elements in the tree and each time size of the subproblem is getting reduced by d which is between 0<d<=0.5

So the number of time we need to multiply d with n so that the problem size get reduced to 1is?

let’s say k times.

n * d^k <=1

now take log both side .

log n + k log d <= 0

log n <= -k log d

so k <= – log n / log d

maximum depth the path will follow which is taking the maximum part of partition

. In this case which is (1 – beta)

k < = – log n / log (1-beta)

and D is correct

Answer 1

Answer  D

Explanation

A maximum depth path  always takes the larger part of partition 

• In question given that always β <=0.5
• So maximum partition will be (1-β ) n

We have to find maximum depth d, means how many times quick sort loop will be executed!!

• One iteration splits the number of elements from n to (β n ) and (1-β)n
• So i iterations reduces the number of elements to β ⁱ n  and (1-β) ⁱ n .

At a leaf, there is just one remaining element,

In case of maximum depth path ( let maximum depth be d)

 (1-β)^d n = 1

 (1-β)^d  = 1/n

Take logarithm on both sides,

d log ( 1-β) = -log n

d = -log n/log ( 1-β)

• Similarly we can find minimum depth d' = -log n/log β

Comments

question is asking for maximum depth ... so ans should be D right  ??

---

Lol..

I thought minimum.....

Corrected..

The calculation part is also added!

---

with each iteration, u mean partition, right....?

---

Taking value of β =0 so that it will become skewed tree and achieve maximum height is this thinking correct ?