As we can see in the problem, j only run from n to 1 for each try of i since one of the condition is j > i. However, the solution that we got is O(n2), which is equal to the complexity of the following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > 0; j–) {

a = a + i + j;

}

}

Can someone explain it to me why?

# I don't understand

**tu-n-nguy-n**#1

**aceone**#2

The outer loop will run N times, and the inner one, worst case, will also run for N times when i = 0.That’s how I calculated it to be O(n**2)

The first loop runs N times.

for i=0 -> second loop runs from n to 0 i.e n times

for i=1 -> second loop runs from n-1 to 0 i.e n-1 times

for i=2 -> second loop runs from n-2 to 0 i.e n-2 times

.

.

.

.

for i=n-1 -> second loop runs from 1 to 0 i.e 1 times

Hence total number of times = n+n-1+n-2+…1+0=n*(n+1)/2

Therefore order of n^2.

So ans is O(n^2)

T(n) = 1 + 2 + 3 … + n = n(n+1)/2

Our goal to find how many times will run inner lool.

Inner loop will run times:

n + n - 1 + n - 2 … + 1 + 0

n * n - 1 - 2 - 3 - 4 … - n

n * n - (1 + 2 + 3 + 4 … + n)

n * n - (n(n + 1)/2)

n * n + (n * n - 1)/2

(n * n + (n * n - 1)/2)*2/2

(2 * n * n + (n * n - 1))/2

(3 * n * n - 1)/2

1.5n^2 - 0.5 ≈ n^2

**MastanPatel**#5

hi our main aim is to find how many time the inner statement :- a = a + i + j; is executing.

so

for i=0; second loop runs from n to 0 i.e n times --> a = a + i + j ran for n time

for i=1; second loop runs from n-1 to 0 i.e n-1 times --> a = a + i + j ran for n-1 time

for i=2; second loop runs from n-2 to 0 i.e n-2 times – > a = a + i + j ran for n-2 time

.

.

.

.

for i=n-1; second loop runs from 1 to 0 i.e 1 times

Hence total number of times the a = a + i + j executed is = n+n-1+n-2+…1+0=n*(n+1)/2

Therefore order of n^2.

So ans is O(n^2)