I don't understand


#1

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?


#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)


#3

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)


#4

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


#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)