CODEWITHSUNDEEP
time-complexityquicksortquickselectmedian-of-medians
Naman Jain
Naman Jain

Reputation: 63

What is the worst case time complexity of median of medians quicksort?

What is the worst case time complexity of median of medians quicksort ( pivot is determined by the median of medians which take O(n) time to find )?

Upvotes: 0

Views: 3281

Answers (1)

Peter Olson
Peter Olson

Reputation: 143037

According to Wiki,

The approximate median-selection algorithm can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n).

This is because the median of medians algorithm prevents the bad partitioning that would occur in naive quicksort on an already sorted array.

Upvotes: 3

Related Questions