Question

What is the worst case time complexity of introsort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(log n)

The question was asked by my college professor while I was bunking the class.

I'm obligated to ask this question of Sorting topic in section Sorting of Data Structures & Algorithms II

Answer 1

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

The explanation is: Worst case time complexity of quicksort is avoided when we implement introsort. Introsort switches to heap sort when there is a possibility of crossing the maximum depth limit.