Question

What is the best 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 posed to me by my college director while I was bunking the class.

My question is taken from Sorting in division Sorting of Data Structures & Algorithms II

Answer 1

Right option is (a) O(n)

For explanation: Best case time complexity of Tim sort occurs when the input array is already sorted. In such a case only one run will be required.