In find the missing number, the solution essentially drags the number that can’t fit at it’s index throughout the array in the worst case and in order to move this number one spot, it has to shuffle around the rest of the array at most once. So shouldn’t the solution be O(n^2)?
For example, first the numbers will get shuffled at index 1 until 8 gets swapped with 0. Then the index will be at 2 and the numbers will get swapped until 8 gets swapped with 1. And so on…
[8, 3, 5, 2, 4, 6, 0, 1]
As for placing all the numbers in the correct position the while loop will swap a total of (n-1) numbers and after placing all the numbers in correct position it will iterate it again to find the missing number. So asymptotically the solution will be O(n).
No, it’s not O(n). You think it’s O(n) because there is a single while loop but it’s really more like two while loops - one for i and one for j.
Hi John I thought the same but in the end figured why it doesn’t count as a nested loop and I will try and explain.
Lets take an example I made up which is similar to the one of the examples:
7, 0, 1, 2, 3, 4, 5, 6
We have 8 numbers in our input from 0 to 7 and essentially missing 8
I have added the numbers in this sequence as it presents the worst case scenario in terms of swapping inside the while loop.
Let’s walk through the iterations manually which I believe will help visualise the time complexity.
Starting point → 7, 0, 1, 2, 3, 4, 5, 6
Iteration 1 → 6, 0, 1, 2, 3, 4, 5, 7
Iteration 2 → 5, 0, 1, 2, 3, 4, 6, 7
Iteration 3 → 4, 0, 1, 2, 3, 5, 6, 7
Iteration 4 → 3, 0, 1, 2, 4, 5, 6, 7
Iteration 5 → 2, 0, 1, 3, 4, 5, 6, 7
Iteration 6 → 1, 0, 2, 3, 4, 5, 6, 7
Iteration 7 → 0, 1, 2, 3, 4, 5, 6, 7
We have performed 7 iterations over an array of length 8 thus O(n - 1)
Our index pointer is still at 0 but now since everything is sorted we wont have any further swaps in subsequent iterations so the we iterate again until i < n thus O(n - 1) the example said O(n) but I say O(n - 1) since we did the 0th when we replaced items.
Finally we iterate once more until we find the missing number thus another O(n)
In total we have O(n - 1) + O(n - 1) + O(n)
I hope that has cleared this for you.