Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?
$\begingroup$
$\endgroup$
3
1 Answer
$\begingroup$
$\endgroup$
5
The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence $$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$ whose solution is $T(n) = O(n\log n)$.
answered May 17, 2019 at 8:24
-
$\begingroup$ Is there any other way by choosing the first element as pivot rather than the median ?? $\endgroup$ May 17, 2019 at 9:12
-
$\begingroup$ It doesn’t have to be the median. It suffices that it break the array into two parts of linear size. $\endgroup$ May 17, 2019 at 9:13
-
$\begingroup$ Yes , I understood , But , is there any other way?? $\endgroup$ May 17, 2019 at 9:15
-
$\begingroup$ Perhaps, but I’m not aware of any such way. $\endgroup$ May 17, 2019 at 9:16
-
$\begingroup$ @SuklavGhosh There is only one way to choose the first element as pivot: you have to... choose the first. And if you do that, the worst case is quadratic. Your question doesn't make sense. $\endgroup$ May 17, 2019 at 12:48
O(nlogn)complexity in all three cases , but I want to do that without converting it to merge sort. $\endgroup$