How to calculate the time complexity of this code?

Question

How to calculate the time complexity of the following algorithm?

int x =0;

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

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

I know that time complexity for nested for loops is equal to the number of times the innermost loop is executed.

like every nested loop that the outer loop is from 1 to n, it should run n times but here we have n-- that makes the algorithm run in better order. actually, I wrote this code in IDE and I printed the final result of x after loops end for different n value and I saw that nearly n times takes that we jump into inner for loop.

so I think that the whole order of this algorithm is O (n) but I am not sure

can someone help me prove it completely?

Answer 1

If you only want the time complexity with big O or big Theta, and let just calculate the upper bound and the lower bound, which are easier cases.

Consider the inner for loop, n will decrease half at the time, or n will become n/2 every time go out of the inner for loop (you already know that right, because j increase 1 unit at the time, n decrease 1 unit at the time, so j and n will meet each other at the middle n or n/2). Things get complicated when we dont know when the code stops, n = ?, but we know that n > 1

Consider this below code (the upper bound):

int x =0;

      for (;n > 1;) {

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

n will become n/2 each iteration until n = 1, so the complexity of the obove code will be n/2 + n/4 + n/8 + ... + 1 = O(n).

The lower bound is even easier, assume that the inner for loop runs only 1 iteration and the code finish, that 1 iteration gives us n/2 operators. So the lower bound would be O(n).

=> The complexity is O(n) overall.

I think the key of upper - lower bound method is leaving out some complex - hard to calculate - unclear changing variable in the code and compare it to the original one

Answer 2

You are correct.

The total number of times n is decreased cannot exceed its original value (i and j are never negative).

Since for each iteration of the inner loop n is decreased exactly once, this gives you upper bound on the number of times this runs, making your code O(n).

You can also see this is a tight bound, since the first time the inner loops runs, it will stop when i >= n, which will happen after ~n/2 iteration, giving a lower bound of Omega(n) as well.