Question

What is the worst case time complexity of library sort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(log n)

This question was addressed to me in an international level competition.

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

Answer 1

The correct option is (c) O(n^2)

Easiest explanation - The worst case time complexity of library sort is the same as that of insertion sort. The worst case time complexity is O(n^2).