educative.io

Time Complexity of cyclic sort

Courses
,
#1

In all the problems related to cyclic sort, the time complexity is mentioned as O(n) which I think is incorrect. Since, the outer loop iterates n times and for each iteration of the outer loop, we swap (say k times) until the right element is put at the correct index. Even when looking at some index which has the right element already, we spend O(1) time to check if the index and the value matches. All together, shouldn’t the time complexity be O(kn). For small values of k, I agree we can say that it is equivalent to O(n). However, if k=n/2, it is O(n^2).

So, any cyclic sort has a worst case of O(n^2) and not O(n) as mentioned.

#2

Yes True. I feel the same. Can anyone confirm why it is O(n)?

#3

The time complexity of the cyclic sort is O(n). The while loop, in the worst case can iterate a maximum of 2n-1 times. As you can see, we are not incrementing the index i when swapping the numbers, this will result in more than ‘n’ iterations of the loop, but in the worst-case scenario, the while loop will swap a total of ‘n-1’ numbers and once a number is at its correct index, we will move on to the next number by incrementing i . So overall, our algorithm will take O(n) + O(n-1) or we can say O(2n-1) which is asymptotically equivalent to O(n).

1 Like