CODEWITHSUNDEEP
time-complexityquicksort
user3661025
user3661025

Reputation: 58

What is the worst case complexity for quick sort?

Assuming that the first element is always chosen as the pivot element, can you please elaborate on where the worst case occurs and its time complexity also

Upvotes: 0

Views: 18128

Answers (1)

sumanth232
sumanth232

Reputation: 587

In Quick sort, if the first element is chosen as the pivot element for partitioning..then
Quick sort exhibits its worst cast complexity - O(n^2) in this case.
More precisely, Quick sort's worst case complexity of O(n^2) is observed when the input to be sorted is in decreasing order or increasing order (if the first elemnet is the pivot element).

The reason for this worst case performance is that, after partitioning , one partition will be of size 1 , and the other will be of size n-1
So, the Time to quick sort 'n' elements T(n) =
Time it takes to partition 'n' elements O(n) + Time to quick sort 'n-1' elements T(n-1)
So, T(n) = T(n-1) + O(n)
=> T(n) = O(n^2)

Upvotes: 7

Related Questions