0
$\begingroup$

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;
        }
    }
$\endgroup$

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.