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?

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?

0

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).

0

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 .

when quetion not mention worst case theta menaning average only .

0

So for what puspose they give Theeta !

http://stackoverflow.com/questions/5126586/quicksort-complexity-when-all-the-elements-are-same

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

You can also see here

http://math.stackexchange.com/questions/22596/quicksort-running-time

0

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

the algorithm cannot take less than nlogn time and algorithm doesnt need to take greater than nlogn time.

theta doesnt mean average

+1

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).**

+1

@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.

0

@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)

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 n^{2} 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(n^{2}) This is my approach any correction is welcomed

52,315 questions

60,428 answers

201,758 comments

95,238 users