Question

What is the worst case time complexity of permutation sort?

(a) O(n^2)

(b) O(n*n!)

(c) O(infinity)

(d) O(n log n)

I had been asked this question in final exam.

This interesting question is from Sorting topic in chapter Sorting of Data Structures & Algorithms II

Answer 1

Right answer is (c) O(infinity)

The explanation is: There is no upper bound to the worst case of this algorithm. It can go on to take a very large amount of time if the array has many elements. So the worst case of this algorithm can be taken as O(infinity).