The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.6k views

The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

  1. $\Theta (n)$
  2. $\Theta (n \log n)$
  3. $\Theta (n^{2})$
  4. $\Theta (n^{3})$
asked in Algorithms by Active (3.7k points)
edited by | 2.6k views

2 Answers

+23 votes
Best answer
As we choose the pivot a median element ... so, every time we are going to have good splits guaranteed so the best case $O(n \log n)$.
answered by Boss (14.2k points)
edited by
+17

every time we are finding median in O(n) times then solving the 2 half array recurcively...

therefore recurrence relation:

T(n) = 2T( n / 2) + O(n)..

0
How is middle and median diiferent ?
+2
What if the array is already sorted? or All the elements in the array are same?

In that case the complexity will be O(n^2) ?
+1

@Dulqar middle means (array size/2)th element whereas median depends upon values in the array.

+2
Here input will be like this

7 6 2 1 3 5 4

So, median element we will get at last.

median means middle element of sorted list
+1
@Srestha this example will take O(n^2). I think O(n^2) will be the right.

 

This e.g break the equation T(n)=T(n-1)+T(0)+ O(n)
+3

@ Brij Mohan Gupta

here question asked about median of array

See this question

https://gateoverflow.in/2048/gate2014-3-14

0
Thanks @srestha
0
@ parikshit If it was the case that all elements in the list are same then in question the word 'median' would not have been used.
+20 votes

To people having doubt on what will be the time complexity when all input values are equal. I had the same doubt for few days and after spending some time on this question here is what i found:

1.There are two standard partition procedure of quicksort, one is lomuto partition which is given in topic of quicksort in cormen in which last element is chosen as pivot and both i and j starts from starting index, second one is hoare's partition which is the original quicksort partition procedure given by hoare who gave quicksort algorithm, this partition procedure is given in problems section of cormen, in this first element is chosen as pivot but i and j starts from opposite ends.

2.Now if u consider lomuto partition then no matter what pivot choosing strategy u follow, be it median or middle or anything the worst case will always be O(n^2) because of input type being all elements with equal values. but if we consider hoare partition and we choose good pivot like median then if all elements are same then we get equal partition so in this worst case can be guaranteed O(nlogn).

here is the reference to geeks for geeks comparing hoare vs lomuto partition: http://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/

what i think is in two gate questions asking time complexity when pivot is median and in other one pivot is 4th smallest element they might be considering hoare partition only.

answered by Active (1.1k points)
+2
good observation , and yes your assumption is correct .

They took Hoare partition as Hoare is who invented the quick sort method so they follow this technique only .
0
Thanks a lot ! Even I had this doubt.
0
thanks vineet ,,,this doubt was very irritating


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

38,079 questions
45,572 answers
132,069 comments
49,045 users