The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then

  1. $T(n) \leq 2T(n/5) + n$

  2. $T(n) \leq T(n/5) + T(4n/5) + n$

  3. $T(n) \leq 2T(4n/5) + n$

  4. $T(n) \leq 2T(n/2) + n$

asked in Algorithms by Veteran (59.4k points)
edited by | 1.7k views
Each of which. means?

If one of the list expands ( > n/5), then the other one shrinks ( < 4n/5) which results in more balanced tree. So T(n) is less in this case.

Here the worst case is when one of the list is of size exactly n/5 & the other exactly 4n/5 resulting in skewed tree. So comparatively T(n) is maximum in this case.

So overall T(n) ≤ T(n/5) + T(4n/5) + n


2 Answers

+22 votes
Best answer

$T(n) \leq T(n/5) + T(4n/5) + n$

One part contains $n/5$ elements
and the other part contains $4n/5$ elements
$+n$ is common to all options, so we need not to worry about it.

Hence, answer = option B

answered by Boss (30.6k points)
edited by

Even in case of n/2, still satisfies the condition; contains at least 1/5th condition;and 2T(n/2) + n < T(n/5) + T(4n/5) + n.

So its safe to go with option B.

@Arjun sir

Why not option d is the answer . Question is saying about number of elements into sublists each of containg atleast one fifth .....  a/c to option d the stack space will be  logn base 2 which is lesser than stqck space of option b  . In option b stack space will be logn base 5/4 which is greater than logn base 2  .  Please correct me  if i am wrong . Thanks
Because we always take close answer
@Arjun sir here option B is exactly equal to the required answer we dont need an approximation right ?? if we take approximation even C will be right as if we increase the number of elements the time complexity will increase and time of our required algorithm will be less than that
+10 votes
The answer is B.

With 1/5 elements on one side giving T(n/5) and 4n/5 on the other side, giving T(4n/5).

and n is the pivot selection time.
answered by Boss (19.7k points)
n is partition time . i think so . is it ???
Yes @xor

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

34,775 questions
41,742 answers
41,388 users