CODEWITHSUNDEEP
c++time-complexity
ZoomIn
ZoomIn

Reputation: 1321

How to determine the time complexity of the nested loop?

I know that first loop is of O(n) and since second is nested loop it is going to be O(n * something). I know that nested loop will be iterating n time and decrementing each time. But how to decide it's time complexity?

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

Upvotes: 2

Views: 1041

Answers (2)

Rob
Rob

Reputation: 2656

technically the time complexity of that algorithm, or number of instructions run, is going to be in the order of:

Sum(N-i) for i=0 to i=N

since the inner loop is run N times each time running just. each iteration running 1 count less.

that sum expanded looks like this:

N + N - 1 + N - 2 + .... 2, 1, 0

which is the same as:

Sum (i) For i = 0 to i = N

this in turn can be solved to something like:

n(n-1)/2 ==> n^2/2 + n/2

And

O(0.5*n^2 + 0.5 n) is effectively O(n^2)

Upvotes: 2

Quimby
Quimby

Reputation: 19113

I assume you mean asymptotic time complexity.

The inner loop will run N-i times and its body is O(1).

Unrolling the outer loop, the complexity is O(N) + O(N-1).... + O(1) which sums up to O(N^2).

Upvotes: 1

Related Questions