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

The Gateway to Computer Science Excellence

+26 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?

- $\Theta (n)$
- $\Theta (n \log n)$
- $\Theta (n^{2})$
- $\Theta (n^{3})$

+32 votes

Best answer

+26

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

+3

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

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

+1

+5

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

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)

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

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.

0

I think answer should be O(n^2) please read the last statement by choosing hoare method we are trying to reduce probability of getting worst but worst case can still happen. Please explain me this.!!

The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.

1) Array is already sorted in same order.

2) Array is already sorted in reverse order.

3) All elements are same (special case of case 1 and 2)

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.

1) Array is already sorted in same order.

2) Array is already sorted in reverse order.

3) All elements are same (special case of case 1 and 2)

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

+42 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.

+4

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 .

They took Hoare partition as Hoare is who invented the quick sort method so they follow this technique only .

0

I think even in Hoares partition, one situation might lead to a O(n^2) complexity.

If all elements are same then the starting index would travel upto ending index trying to find an element greater than pivot(which it obviously won't find).

So the division would be T(n) = T(n-1) + T(0) + cn. [One group will contain (n-1) elements and the other 1 element].So run-time would be O(n^2).

Correct me if I'm wrong here

If all elements are same then the starting index would travel upto ending index trying to find an element greater than pivot(which it obviously won't find).

So the division would be T(n) = T(n-1) + T(0) + cn. [One group will contain (n-1) elements and the other 1 element].So run-time would be O(n^2).

Correct me if I'm wrong here

+3

Another fabulous link validating your point:

https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

+2 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

The "median" is the "middle" value in the list of numbers. To find the median, your numbers have to be listed in numerical order from smallest to largest, so you may have to rewrite your list before you can find the median.

Since the given input is not sorted, so the time complexity to find the median is O(n) in an unsorted array.

Since the given input is not sorted, so the time complexity to find the median is O(n) in an unsorted array.

52,217 questions

59,905 answers

201,094 comments

118,142 users