+1 vote
948 views

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

| 948 views
0
yes, u r right

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
If array is not sorted , then how u find median in nlogn time?
0
actually here best choice is option (B) if we consider array is sorted is worst case complexity by choosing first element as pivot will be O(n^2) -so option(A) is not correct in this case

in case of median element worst case time complexity will be O(nlogn)-so option (B) is correct

for option C,let size of array is 5 ,and elements are 2,2,2,2,2 so the mean will be 2 so if we consider it as last element as pivot  in this case worst case complexity is O(n^2)-so option C is incorrect
0
@srestha , we are reuired to find the median of only 3 elements here, which i think will take O(1) time .Also, the question mentions worst case of quick sort which generally takes place when array is sorted.So, median can be found in O(1) time.
+1
worst case doesnot mean sorted array

But when finding median u require a sorted array only
0
thnks for your insights.... will look into this...
0

whats the significance behind saying "Median of first, last and middle elements"? I mean median of any odd number of elements will be middle element