Why is the time complexity of this code O(N)?

Question

I thought the time complexity of the code below is O(n^2) or O(n*logn).

int j = 0;

for(i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}

However, the answer page says it is O(n).
I can't understand why it becomes so.
My (silly) opinions were the following:

The time complexity is O(n^2) since there are two loop running n times. arr[i] < arr[j] may affect the while loop, but it doesn't matter.
The time complexity is O(n*logn) since the while loop may run less than n times because arr[j] can be smaller than arr[i] during the loop. As a result, while loop would run for log(n) times.

Could you explain why was my answer wrong and why the correct time complexity is O(n)?

Note that j is newer reset to 0. So the inner loop can only run O(n) times in total — MTilsted
The inner loop will run only once as you don't reinititialize j to 0. — Actarus

Jon Hanna Jon Hanna · Accepted Answer · 2017-10-01T10:57:00

for(i = 0; i < n; ++i)

Loops n times.

while(j < n && arr[i] < arr[j]) {
    j++;
}

Loops up to n times in total. Note that j is only ever incrementing for the entire loop of i, so it being an inner loop doesn't make it a higher order, as it still can only go from 0 to n for the entire set of loops.

So it's O(2n) = O(n)

Why is the time complexity of this code O(N)?

2 Answers