Question

What is the average time complexity of Tim sort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(log n)

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

My enquiry is from Sorting topic in chapter Sorting of Data Structures & Algorithms II

Answer 1

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

Explanation: Average time complexity of Tim sort remains to be O(n log n). It is the same as the average case complexity of merge sort.