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

CodePudding user response：

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

CodePudding user response：

Another way to see it's O(n): You only enter the inner loop body if j <= n, and since j is positive, n must also be positive. But you decrease n every time, which you can only do O(n) times (where n is the starting value) and still have n positive.