Question

What is the average time complexity of the median of three quick sort?

(a) O(n log n)

(b) O(n^2)

(c) O(n^2 log n)

(d) O(n log n^2)

I have been asked this question by my college professor while I was bunking the class.

The above asked question is from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

Correct choice is (a) O(n log n)

To explain: The average case time complexity of median of three quick sort is the same as that of a standard quick sort as randomized quick sort only helps in preventing the worst case. It is equal to O(n log n).