retagged by
5,144 views
4 votes
4 votes

Suppose we have a O(nlogn) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

  1.   Worst case time complexity of modified quick sort is same as that of original quick sort.
  2.   Worst case time complexity of modified quick sort is better than that of original quick sort.
  3.   Average case time complexity of modified quick sort is same as that of original quick sort.
  4.   None of the above
retagged by

2 Answers

2 votes
2 votes

First, let me give a brief definition of Median element of an unsorted array. A Median element of an unsorted array is nothing but the Middle element of the sorted array. So, the question asks us to assume that a modified quick sort algorithm makes use of a Median finding algorithm for selecting its pivot element (not the first, last or random element of the unsorted array). This means when the partition algorithm on given array finishes the pivot element will be at the mid of the array. Thus the array will be partitioned into two equal half with utmost certainty.

Because of this modification, the recurrence relation of quick sort will be

$$T(n) = O(nlogn) + O(n) + 2T(n/2)$$

Apply Master's Theorem to get 

$$T'(n) = O(n\log^2(n))$$

If we compare $T'(n)$ with the worst case time complexity of original quicksort alogirthm i.e., $T(n)=O(n^2)$, we see that $T'(n)$ surely wins.

Now it is worth mentioning explicitly why the modified algorithm performs better in the worst case. If we execute modified algorithm on an already sorted array, in each iteration the pivot selected is the one that is in the middle of the array (with no swaps operations, hardly matters though) and divides the array into exactly two parts for further iterations.

However, in case of original quicksort algorithm, it either selects the first or last element as the pivot, which thereby causes the array to partition into two parts with zero elements on left (or right based on pivot selection) and rest all the elements on the other side of the pivot. This degrades the performance of the algorithm.

Thus the answer is - (2) Worst case time complexity of modified quick sort is better than that of the original quicksort algorithm.

1 votes
1 votes

For Modified QuickSort Recurrence Relation will be :

T(n) = 2T(n/2) + nlogn --> here done n/2 as after finding median & choosing it as pivot it divides in two halves.

So by master theorem complexity is Θ(n(log^2 n))

Now our orginal Quicksort has worst case time complexity --> O(n2).

So we can easily that worst case time complexity of Modified Quicksort is better than Original Quicksort. Hence option 2 is correct choice.

Related questions

0 votes
0 votes
1 answer
2
Purvi Agrawal asked Oct 13, 2018
3,716 views
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as thepivot. Calculate the worst case time complexity of the algorithm.
3 votes
3 votes
1 answer
4
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...