educative.io

Isn't the time complexity of Cyclic Sort O(n^2) rather than O(n)?

Courses
,
#1

Everywhere I look online says Cyclic Sort has a time complexity of O(n^2), though the solutions say that it’s O(n). Wouldn’t you be better off just sorting the array using Quick Sort or Merge Sort?

#2

Hi @Nick_Vecchioni

In the example discussed in the lesson, we are given an array with all the numbers from 1 to n, with no duplicates or missing values. In this case, we just need to place every value at its correct index, which results in a complexity of O(n).

Hope this helped!

1 Like
#3

Thanks!

1 Like