Question

What is the best case time complexity of strand sort?

(a) O(n)

(b) O(n log n)

(c) O(n^2)

(d) O(n^2 log n)

I got this question in an internship interview.

This intriguing question originated from Sorting topic in section Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (a) O(n)

Best explanation: Best case time complexity of strand sort is O(n). It occurs in the case where the input array is already sorted.