Question

What is the worst case time complexity of Tim sort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(log n)

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

I'd like to ask this question from Sorting in chapter Sorting of Data Structures & Algorithms II

Answer 1

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

Easy explanation - Worst case time complexity of Tim sort is O(n log n). It is because the worst complexity of merge sort is O(n log n) and insertion sort is only applied for small arrays.