Question

What is the average case time complexity of cycle sort?

(a) O(n^2)

(b) O(n log n)

(c) O(log n)

(d) O(n)

I got this question at a job interview.

I would like to ask this question from Sorting topic in division Sorting of Data Structures & Algorithms II

Answer 1

The correct option is (a) O(n^2)

The explanation is: The average case performance of cycle sort is O(n^2). It is because it has to make n comparisons for each element of the array.