I don't understand how the time complexity for this algorithm is calculated

Question

int j=0;
for (int i=0; i<N; i++) 
{
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1; 
}

This code is said to have the time complexity of O(n), but I don't really get it. The inner loop is executed N times and the outer should be also N times? Is it maybe because of the j = 0; outside the loop that is making it only run N times?

But even if it would only run N times in the inner loop, the if statment check should be done also N times, which should bring the total time complexity to O(n^2)?

Answer 1

The reason why this is O(n) is because j is not set back to 0 in the body of the for loop.

Indeed if we take a look at the body of the for loop, we see:

while ( (j<N-1) && (A[i]-A[j] > D) )
    j++;

That thus means that j++ is done at most n-1 times, since if j succeeds N-1 times, then the first constraint fails.

If we take a look at the entire for loop, we see:

int j=0;
for (int i=0; i<N; i++) {
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1;
}

It is clear that the body of the for loop is repeated n times, since we set i to i=0, and stop when i >= N, and each iteration we increment i.

Now depending on the values in A we will or will not increment j (multiple times) in the body of the for loop. But regardless how many times it is done in a single iteration, at the end of the for loop, j++ is done at most n times, for the reason we mentioned above.

The condition in the while loop is executed O(n) (well at most 2×n-1 times to be precise) times as well: it is executed once each time we enter the body of the for loop, and each time after we execute a j++ command, but since both are O(n), this is done at most O(n+n) thus O(n) times.

The if condition in the for loop executed n times: once per iteration of the for loop, so again O(n).

So this indeed means that all "basic instructions" (j++, i = 0, j = 0, j < N-1, etc.) are all done either a constant number of times O(1), or a linear number of times O(n), hence the algorithm is O(n).