Why is complexity O(n) + O(n-1)

bee1 · September 14, 2022, 3:22am

The time complexity description says it will be O(n) + O(n-1) which is equal to O(n).
O(n) may be correct but why are we saying time complexity will be O(n) + O(n-1)?

Would’nt it be O(n)+O(n-1)+O(n-2)+O(n-3)+…O(1)
because worse possible scenario applies for each index.
for i=0 we have to swap all items in the array
for i=1, we have to swap all items in the array minus 1 item on index 0 that was sorted in the previous step. So this step’s complexity will be O(n-1)

for i=2, we have to swap all items in the array except the first 2 indices that were sorted in previous steps. So this step’s complexity will be O(n-2)

for i=3, we have to swap all items in the array except the first 3 indices. So this step’s complexity will be O(n-3)
and so on.

so total complexity will be O(n) + O(n-1) + O(n-2) + O(n-3) + …
asymptomatically I believe this is still O(n) (can you verify that?)
but I just wanted to clarify the breakdown because in your answer it only had O(n) + O(n-1) .
Not the whole series.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Cyclic Sort (easy) - Grokking the Coding Interview: Patterns for Coding Questions

Muntha_Amjad · September 14, 2022, 6:16am

Hi @bee1, Thanks for reaching out to us.
Although 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), which is asymptotically equivalent to O(n).

Secondly, you are right, but overall time complexity is still O(n); that’s why in the lesson we only discussed O(n) + O(n-1) and the same pattern O(n-2) + O(n-3) +… will be followed as you said.

Hope it will clear your confusion, Happy Learning