Question

Time complexity of sleep sort can be approximated to be ___________

(a) O(n + max(input))

(b) O(n^2)

(c) O(n log n + max(input))

(d) O(n log n)

The question was posed to me in semester exam.

Question is from Sorting topic in portion Sorting of Data Structures & Algorithms II

Answer 1

Right choice is (c) O(n log n + max(input))

Explanation: As the sleep() function creates multiple threads by using priority queue which takes n log n time for insertion. Also the output is obtained when all the elements wake up. This time is proportional to the max(input). So its time complexity is approximately O(n log n + max(input)).