The Gateway to Computer Science Excellence
0 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—
A. T(n) <= 2T(n/5) + n  

 B. T(n) <= T(n/5) + T(4n/5) + n

C. T(n) <= 2T(4n/5) + n    

D. T(n) <= 2T(n/2) + n

The Answer to this question is B. My doubt is that why can't the answer be C? My logic is that if there are (n/5) elements on one side and (4n/5) on the other, then T(n)= T(n/5) + T(4n/5) + n. Here, 4n/5 > n/5 so definitely, time taken will be less than 2T(4n/5) + n, if elements are more than (n/5)( since it is given 'AT LEAST').

Where am I going wrong?
closed as a duplicate of: GATE2008-43
in Algorithms by
closed by | 623 views
C can be answer you are right but B gives more accurate analysis then C
True . @fzx

1 Answer

0 votes
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
52,315 questions
60,427 answers
95,235 users