Misunderstanding small details w/ nested for-loop time complexity analysis... How to tell O(n) and O(n²) apart

Question

For the algorithm below:

 int x = 0;
 for (int i = 0; i < n; i++)
     for (j = 0; j < n; j++) {
         if (j < i) j = j + n;
         else x = x + 1;
      }

So for this algorithm, my thought process goes like this:

The inner-loop performs n iterations for j when i=0. However, for every value of i=0,1..n-1, j will only perform one iteration because the if-statement will evaluate to true and end the inner-loop.

Here is my source of confusion:

Since the outer-loop will perform n iterations no matter what, and since the inner loop performs n iterations when i=0 (very first iteration), how come the big-Oh time complexity isn't O(n²) and is instead, O(n) if the loops are nested and both perform n iterations in the very first iteration?

Answer 1

You have a line that says if (j < i) j = j + n; which essentially breaks out of the loop (when j < i), and since the inner loop starts at 0, this will trigger on the first iteration every time (except the first time), making it run in constant time.

You essentially only have one loop here. The code can be rewritten as

int x = 0;
for (int i = 0; i < n; i++) {
    x = x + 1;
}

which makes it clear why it is O(n).