Question on time complexity!

[lost110]

 int a = 0;
for (i = 0; i < N; i++) // Here the order is N
 {
for (j = N; j > i; j--)//  Here J is decrementing from N + (n-1) + (n-2)....0 So:  n(n+1)/2
 {
    a = a + i + j;
  }
} 

So won't it be the order of (N)*(N)(N+1)/2 = N^3?? because the loops are nested so multiplied...but the answer at geeks for geeks is N^2
Thanks!

[jonnin]

nested loops being multiplied needs to be very carefully understood or you will get in trouble. If you have a 2-d matrix with N items, and you double loop to access it, the number of things you do is still N, right? There are other examples as well ... the inner loop could execute exactly 3 times no matter what, so double loops but N complexity. You have to look at the exact problem and exact code carefully.

speaking of which...
you just did not understand the math here.
each time through the second loop, it runs about N/2 times on the averages. the smallest loop happens 1 time, the biggest happens N times, but on the average, it happens N/2 times.
the outer loop is N. N*N/2 -> N*N complexity. Does that make sense? What you tried to do was take ALL THE RUNS OF THE INNER LOOP and then do those N times, which is indeed N*N*N but that is not what the code does. It only does ONE run of the inner loop each time :)

[Ganado]

Also, for simple things like this that don't involve too much complexity (e.g. no logs, sqrts, 2^n's, etc), you can often see the pattern just by having a counter variable. Obviously this isn't a very rigorous way of doing it.

// Example program
#include <iostream>

int complexity_counter(int N)
{ 
    int counter = 0;
    for (int i = 0; i < N; i++) 
    {
        for (int j = N; j > i; j--)
        {
            // loop doesn't depend on a, so that logic is removed for brevity
            counter++;
        }
    } 
    return counter;
}

int main()
{
    for (int i = 0; i < 20; i++)
    {
        std::cout << i << ", " << complexity_counter(i) << '\n';   
    }
}

0, 0
1, 1
2, 3
3, 6
4, 10
5, 15
6, 21
7, 28
8, 36
9, 45
10, 55
11, 66
12, 78
13, 91
14, 105
15, 120
16, 136
17, 153
18, 171
19, 190

You can see each output delta increases by 1 each time, so you can easily tell it's quadratic.

[jonnin]

in practice, I usually do go with a counter.

[lost110]

https://www.geeksforgeeks.org/practice-questions-time-complexity-analysis/
Its question number 2 and the explanation is given. N + (n-1) + (n-2)....0 So: n(n+1)/2 This equation is for sum of series numbers from 0->N. So thats why I am saying that when we open the brackets we get n^2. And later we also have to consider the outer loop order i.e n.
So n*n^2= n^3

[Ganado]

I'm not following. The link you gave shows 4 possible choices for question 2:

O(N)
O(N*log(N))
O(N * Sqrt(N))
O(N*N)

None of those are O(N^3). [Okay well technically big-O notation is the upper-bound... but let's not get too confused here]

The big-O notation for complexity is as N approaches infinity, for the algorithm as a whole, it's not the sum of separate trials from 0 to N.

The inner-most logic runs

N + (N – 1) + (N – 2) + … 1 + 0

times.
AKA: It takes N + (N – 1) + (N – 2) + … 1 + 0 iterations to compute the result of the computation.
So the code as a whole has a complexity of O(N + (N – 1) + (N – 2) + … 1 + 0), which reduces to O(N*N).

[jonnin]

This equation is for sum of series numbers from 0->N. Sure it is. So what?

say n = 100.
say i = 10.

for (int j = N; j > i; j--)

this inner loop becomes
for(int j = 100; j > 10; j--)
how many times does it execute? on THIS iteration?!
is it: n(n+1)/2 or 100(101)/2 times?
or is it about N times (90, or whatever)?

I said this earlier, Ill try it again. You are counting the inner loop as if the inner loop did this ( n(n+1)/2) once for every outer loop. It does not. It does a small part of that for each outer loop. the formula you are looking at is for the inner loop after it has been executed once for each of the outer loop runs. You are double counting it. at the end of the day, both loops combined produce your ( n(n+1)/2) which is ... N*N. You can get there more formally (see above) if you didn't recognize the formula.