How can the time complexity for this algo be O(N)?

Question

The source from which I got this code claims that its time complexity is O(N), but how can that be? It appears to me that the time complexity should be O(N²).

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;
}

The inner while loop will be called N times under which j increments at most N times so in total it will increment at most N² times. Therefore, the time complexity should be O(N²). How can it O(N) also be okay for this algorithm?

Answer 1

j is only assigned at line 1 (assigned zero). After that line j is only touched at line 4, to be incremented.

Like so, in the worst case, in the first iteration of the for loop when i = 0 and A[i] - A[j] > D will always evaluate to true, j will be incremented until reaching N. After that, the other iterations of the for loop will all be O(1) since the inner while loop will never be executed.

In the whole execution of the algorithm, j is incremented no more than N times, like the explanation you sent said.