Time complexity of dependent nested loops

Question

I was trying to find the time complexity of this nested loop

for (i = 1; i <= n; i++) {
  for (j = 1; j <= n; j++) {
    n--;
    x++;
  }
}

If there wasn't a n-- it would be n*n , O(n²) right?

But what if n reduces every time second loop runs?

What's the time complexity and big O of this nested loop?

If I consider n = 5, x equals 4, the second loop runs 4 time

Answer 1

The time complexity of the code is O(n). n is reduced by half for every iteration of the outer loop.

So we have n/2 + n/4 + n/8 + n/16 + ... + n/2^k = O(n)

where k is the number of iterations of the outer loop (basically i).

Note that the time complexity is independent of x.

If there wasn't a n-- it would be n*n , O(n²) right?

Yes