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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,439 comments

100,710 users