CODEWITHSUNDEEP
time-complexity
Vktr
Vktr

Reputation: 89

When finding the time complexity for a nested loop, do you consider the outer loop even when the inner loop stops running?

Consider this code:

int sum = 0;

for(int i = 0; i < N*N; i++)
{
    for(int j = i; j < N; j++)
    {
        sum++;
        System.out.println(sum);
    }
}

I've always known that to find the time complexity is to find how many times the inner-loop will be executed. But in the above code, the inner loop will keep running until i reaches N. When i exceeds N, the inner loop no longer updates the value of sum. But the outer loop will keep on running to completion.

So since the inner loop keeps running until i reaches N, shouldn't the time complexity of this code be O(N^2)? The solutions say that the time complexity is O(N^3).

Upvotes: 0

Views: 283

Answers (1)

Khalifa Abourawi
Khalifa Abourawi

Reputation: 9

O(n^3) is correct!

For each iteration of the outer loop (i), the inner loop (j) will iterate N times, then it will exit the loop. The outer loop will increase i=0 to i=1 then execute the inner loop again (which iterates another N times), and will keep doing this until i = N*N. So you can say the inner loop iterates N times per outer-loop-iteration.

The outer loop starts at i=0 and iterates N*N times.

If the inner loop loops N times each time the outer loop loops, and the outer loop iterates N*N times, the total number of iterations of the inner loop is:

 (# of inner iterations per outer iteration) * (# of outer iterations)
 = (N) * (N*N)
 = N^3

Upvotes: 0

Related Questions