Hello everyone,
The solution states that the time complexity is:
O(n) + O(n - 1) + O(n) => O(n)
Where are we getting the first O(n)? I understand that the second O(n - 1) is coming from the worst-case number of swaps and the last O(n) is coming from the final iteration to check for the missing number.
Thanks!
Hello @Eric_Y_Kim,
The algorithm discussed in the lesson follows the Cyclic Sort pattern as discussed here. First O(n) in the complexity comes from the fact that the while loop swaps a total of n-1 numbers, and we do not increment i until the number is not at its correct index. Once the number is at its correct index, only then do we increment i. Following this, we iterate over the array linearly, one step at a time, until all the numbers are at their correct indexes. Hope this answers your query. Feel free to ask any questions if you still have any confusion.