1,936 views
0 votes
0 votes

@arjun sir
why is quick sort with median as pivot not in practice even though it can sort the worst case list in O(nlogn) time?
median can be found in O(n) time and this divides list into two halves.
recurrance relation becomes
T(n) = 2T(n/2)+O(n)
which gives O(nlogn)
why do we still say worst case TC of quick sort is O(n^2) when median as pivot can do it in O(nlogn) time?
http://www.geeksforgeeks.org/can-quicksort-implemented-onlogn-worst-case-time-complexity/
 this link says we dont implement it bcoz "The hidden constants in this approach are high compared to normal Quicksort"
but why are we caring about constants here? 

1 Answer

0 votes
0 votes

Because its name is Quick sort, SO you cannot neglect constant, it will loose its property

and its not exactly O(n) it is cn c can be 10,100,1000,10000

as constant increase n will approach n2 Since recurrence relation does not accurately tell us constant required it is just an tool for analysis 

T(n)= 2T(n/2)+Cn

no if N= 10000 and C=10000

then complexity will be O(n2) This is my approach any correction is welcomed

Related questions

3 votes
3 votes
1 answer
1
iarnav asked Jan 14, 2018
2,460 views
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the...
3 votes
3 votes
3 answers
2
Sourajit25 asked Sep 3, 2017
1,612 views
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
3 votes
3 votes
1 answer
3
SHALINI PORWAL asked Aug 10, 2017
1,353 views
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?
2 votes
2 votes
3 answers
4
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.