+ 1

What is quick sort best case and worst case complexity ?

When input set is list1 =[1,2,3,4] sorted data When input set is list2 = [5,4,3,2,1] Does the complexity is differ in both cases and which has least complexity I know the best case complexity of quick sort is (n log n)

18th Sep 2019, 1:38 PM
Preity
Preity - avatar
2 ответов
+ 4
It's O(n log n) in both cases. The best, the average and the worst complexity of Quick Sort is O(n log n).
18th Sep 2019, 1:52 PM
Diego
Diego - avatar
+ 2
~ swim ~ Diego thanks @swim three way partition means choosing pivot element as first, last and median possibly equal key can be chosen randomly by choosing may be the inplace or optimal quick sort as I know Thanks for your confirmation Does sorted array take O(n²) in worst case or it can take O(n) as no swaps are performed in the first list so in general sorted array takes more time or not sorted one in quick sort
18th Sep 2019, 2:15 PM
Preity
Preity - avatar