The Gateway to Computer Science Excellence
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?
 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? 

in Algorithms by | 774 views
Anusha find median in elements, 10,10,10,10,10,10,10,10 till n times.  You Find median in O(n) time will it be usefull. Can u garunteed to get time O(nlogn).
ok then answer to this question according to u?

all options are asking average case there no one saying worst case. if they use O(n^2) then yes it will be answer.

when quetion not mention worst case theta menaning average only .
no theta is not for average!

So for what puspose they give Theeta ! 

chech here. without modification we can not go for O(nlogn). as i think.

You can also see here

theta is to tell that algorithm running time  is O(nlogn) and omega(nlogn)..
the algorithm cannot take less than nlogn time and algorithm doesnt need to take greater than nlogn time.
theta doesnt mean average
isnt omega says best case and big oh says worst case. thwn Theeta?

in the link given by you, 
second answer says
The answer depends on how you are selecting the pivot. If you follow the algorithm present in the CLSR which always selects the last element as the pivot then it would result in the equation T(N)=T(N−1)+NT(N)=T(N−1)+N and hence T(N)=O(N2)T(N)=O(N2) else if you select the median element as the pivot every time the equation will become T(N)=2T(N/2)+NT(N)=2T(N/2)+N which would result in T(N)=Θ(NlogN)T(N)=Θ(Nlog⁡N).

@Anusha you are correct. Theoretically that is true. But doing it practically is difficult - O(100000) is O(1) but is worse than O(n) for small n. So, in a computer there is a limit for constants which can be used efficiently.

@Arjun please look at it:
If every time a median which takes O(n) to be found, is chosen as pivot, then Quick Sort takes theeta(nlogn) time complexity. 
My question is if all the elements are same, will still be this median Quick Sort also have time complexity as theeta(nlogn)?? 
Can you please run the algo for 10, 10, 10, 10, 10 and show that TC is not O(n^2)

if all elements are same what is the median?
1st element or any element .
i think middle element will be the median as the list is sorted.
Arjun sir since all element same then choose any element is middle na?
What about the value returned by the median-of-median algorithm in CLRS?
Sir simple median is asking here or median of median.
if median is taken as pivot,is that be always support worst case?

1 Answer

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

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,428 answers
95,238 users