search
Log In
1 vote
552 views
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($n^{2}$)
b.O(nlogn)
c.O($n^{2}$logn)
d.O(nloglogn)
in Algorithms
edited by
552 views
0
It should be O(nlogn) in worst case because, selecting median as pivot means it will be always  placed at the middle after applying partition algorithm.
0
B is the correct option

Because for every split occur at the middle .
0
what is that means[ Pivot is the median of set of 3 elements ].

4 Answers

1 vote
Worst case would be Θ($n^2$) because input array given is already sorted.

reshown by
0
i think O(nlogn) is right answer....
1 vote
B should be the correct option.
1 vote
Option B is the correct answer.

lets consider an array 1,2,3,4,5

according to the question median of an array = median(1,3,5)= 3.

so the array is divided into almost equal halves and for that time complexity would be O(nlogn)
0 votes
option B) O(nlogn) is correct , because everytime array is divided into almost equal parts.

Related questions

0 votes
1 answer
1
416 views
Is there any standard way to sort in Quicksort or what all matters is PIVOT getting placed at its correct position thats it? I mean if only pivot condition then 3!*3! for both left and right elements but if any standard then each of the left and right parts ... fixed way that after 1st pass the array will remain as it is and only those elements compared with the minimum will be getting swapped.
asked Dec 26, 2018 in Algorithms Markzuck 416 views
–1 vote
0 answers
2
290 views
Which of the following sorting algorithm represented by above code?
asked Dec 19, 2018 in Algorithms Abhishek Kumar 38 290 views
2 votes
1 answer
3
333 views
An array of size n is known to be sorted except for the 1st k elements and the last k elements, where k is a constant. which of the following algorithm is the best choice for sorting the array A? Quick Sort or Insertion Sort? given answer is the insertion sort, and i know it should ... the value of k), and it will take O(klogk) in average case and O(k^2) in the worst case. what's wrong in that?
asked Dec 15, 2018 in Algorithms aambazinga 333 views
...