How to calculate the time complexity if the upper bound is decreasing as well?

Question

For example if the condition is i<=n, and the n is decreasing in the loops, how can i calculate the time complexity? Lets say we have nested loops like below:

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

Or if the decrement of n is being done in the inner loop:

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

Answer 1

You do a bit of maths. To avoid confusion, assume we were given N and we first let n = N.

The outer loop will end when both i and n equal N/2. The number of iterations in the inner loop goes from N to N/2. So the inner loop is executed N/2 times, with 0.75N iterations on average, for a total of $0.375 \cdot N^2$ iterations.

Answer 2

In your second example, with a given n at the start of the inner loop, there will be n/2 iterations until both j and n are set to the original value of n, divided by 2.

So you have n/2 iterations with i = 1, n/4 iterations with i = 2 etc. with a total of less than n iterations.

Again, like in the first answer, you analyse what the code does and that will give you the answer. There’s no recipe.