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?
ok then answer to this question according to u?
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
in the link given by you,http://math.stackexchange.com/questions/22596/quicksort-running-time
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)=Θ(NlogN).
@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)
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
no if N= 10000 and C=10000
then complexity will be O(n2) This is my approach any correction is welcomed