3,387 views
3 votes
3 votes

Quick sort gives O(nlogn) worst case performance if the pivot is selected as:

a) First element of the array

b) Median of first, last and middle elements

c) Arithmetic mean of the elements

d) None of these

 

Now, the answer is given as Option (b). But, as far as I know complexity of quick sort depends on order of elements and not on pivot element. So, answer should be option (d) i.e None of these

Correct me if I am wrong

2 Answers

4 votes
4 votes

This is such a beautifully formed question.

The question says ""Quick sort gives $O\left ( nlogn \right )$ in worst case" .

The worst case of quick sort occurs when the array is sorted and one of the extreme elements is chosen as pivot.

Since, the question mentions worst case, we need to consider the case of sorted input. 

 

Now lets analyze the options:

a) First element: This is clearly out of the game as this will give time complexity of $O\left( n^{2} \right )$.

 

c)Arithmetic mean: This number depends upon the distribution of numbers.If the numbers are uniformly distributed in an interval, then the arithmetic mean would probably lie near the centre of the array.But this may not be the case always.Hence,this option is also rejected.

 

b)Median of 1st, last and middle element:If the input is sorted, then the median of these three elements will be the middle element itself.Also, in sorted array, the middle element is median itself.

So in any case, the median will give a half-half partitioning when we consider the worst case.

This half-half partitioning will lead to $O\left ( nlogn \right )$ in worst case.

 

Important point: The median of entire input may require $O\left(n\right)$ time.But here we only need to find median of those 3 elements and that too when the array is sorted which will take constant time.

 

Therefore, option B seems best choice.

 

- Happy Learning

0 votes
0 votes
Time complexity of quick sort depends on how the pivot divides the list if the pivot divides the list from middle the the list will broke down in two half and following this recursively it will give complexity of nlogn but if the list is divided in to n-1 and 1 then following this ...complexity will be n^2 ... So if the pivot is median of the list then it will surely divide the list into two equal halves this nlogn... But option b looks complicated as it is median. Of first last and middle no. Not the whole list

Related questions

3 votes
3 votes
1 answer
1
iarnav asked Jan 14, 2018
2,460 views
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the...
3 votes
3 votes
3 answers
2
Sourajit25 asked Sep 3, 2017
1,613 views
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
3 votes
3 votes
1 answer
3
SHALINI PORWAL asked Aug 10, 2017
1,353 views
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?
2 votes
2 votes
3 answers
4
LavTheRawkstar asked Apr 15, 2017
1,186 views
With quick sort The results after first partioning of the given array. A = (2,8,7,1,3,5,6,4,9).Analysis the time complexity of Quick sort in the best case.