edited by
53,239 views
44 votes
44 votes

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})$
edited by

4 Answers

Best answer
49 votes
49 votes
When we choose the median as the pivot element, we guarantee the split in half, so the best case of quick sort.

$$T(n) = 2T(\frac{n}{2}) + O(n) =O(n \log n)$$

Correct Answer: $B$
edited by
64 votes
64 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.

7 votes
7 votes

Note: Middle element is nothing but $\dfrac{n}{2}^{th}$ element but Median is $\dfrac{n}{2}^{th}$ smallest element.

$\underbrace{O(n)}$      

Median

$+$

$\underbrace{O(1)}$

Swap with

last element

$+$

$\underbrace{O(n)}$

partition

algo

$\underbrace{2T\left(\dfrac{n}{2}\right)}$

equally

divides


$T(n)=O(n)+O(1)+O(n)+ 2T\left(\dfrac{n}{2}\right)$

$T(n)=O(n)+ 2T\left(\dfrac{n}{2}\right)$

$T(n)=O(nlogn)$

0 votes
0 votes

Just to add fine details:

i) Median: Middle most element in a sorted seqeunce. O(nlogn)

ii) Middle: Middle element in the given list. Note it is different from median element. O(n^2)

Answer:

Related questions

39 votes
39 votes
4 answers
1
Rucha Shelke asked Sep 17, 2014
25,176 views
Which one of the following in place sorting algorithms needs the minimum number of swaps?Quick sortInsertion sortSelection sortHeap sort
59 votes
59 votes
7 answers
2
Rucha Shelke asked Sep 16, 2014
31,355 views
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree
33 votes
33 votes
7 answers
3
44 votes
44 votes
5 answers
4
Rucha Shelke asked Sep 16, 2014
20,571 views
In a binary max heap containing $n$ numbers, the smallest element can be found in time $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$