2,286 views
1 votes
1 votes

Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort?

a)$O\left ( n^{2} \right )$

b)$O\left ( n log n \right )$

c)$O\left (n^{2} log n \right )$

d)$O\left (nlog log n \right )$

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------

My doubt is here for every 3 element we have to apply quick sort, rt? So, in modified quick sort we can do first quick sort and then merging using merge sort.rt?

1 Answer

2 votes
2 votes

Here pivot is selected based on : the median of first element , middle element and last element which is nothing but the middle element only and this is the median also as we are given the input array as the sorted array..So this is the median also of the entire array to be precise..

Hence the division is prespecified as this is the pivot hence will divide into 2 equal subarrays after applying partition..Hence the recurrence will be :

          T(n) = 2T(n/2) + O(n)  [ As O(n) for partition ]

 ==>   T(n)  = θ(nlogn)  [ As best case = worst case = average case as median is selected as pivot here ]

Hence B) is the correct answer..

Related questions

4 votes
4 votes
3 answers
1
Swati verma asked Jun 21, 2017
7,584 views
Time complexity of quick sort when we take pivot from the middle element
1 votes
1 votes
1 answer
2
AJAY KUMAR ARYAN asked Jan 8, 2016
1,078 views
Q:- which one is the best among heap sort ,quick sort and merge sort in terms of complexity ? please answer with explanation!!
4 votes
4 votes
2 answers
3
amarVashishth asked Jul 21, 2015
755 views
Given an instance of custom quick sort in which the Pivot element is always the $\left( \frac{n}{4} \right)^{th}$ smallest element. GIven a large array as input and an im...
4 votes
4 votes
1 answer
4
akankshay asked Mar 9, 2016
15,730 views
the worst case time complexity of quicksort for an elements when the median is selected as the pivota. o(n^2)b.o(n)c.o(nlogn)d.o(logn)