Question

What is the average time complexity of randomized quick sort?

(a) O(n log n)

(b) O(n^2)

(c) O(n^2 log n)

(d) O(n log n^2)

This question was addressed to me in examination.

This intriguing question comes from Sorting in chapter Sorting of Data Structures & Algorithms II

Answer 1

Right option is (a) O(n log n)

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