Q:

Big-O for-loop runtime analysis

 int n = 500;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            sum++;

My guess is this is simply a O(N^2), but the j < i is giving me doubts.
int n = 500;
     for(int i = 0; i < n; i++)
        for(int j = 0; j < i*i; j++)
            sum++;

Seems like an O(N^3)
  int n = 500;
     for(int i = 0; i < n; i++)
        for(int j = 0; j < i*i; j++)
            if( j % i == 0 )
               for( k = 0; k < j; k++ )
                  sum++

O(N^5)?
So for each loop j has a different value. If it was j < n*n, it would've been more straight forward, but this one is a tricky one, so please help. Thanks. 

A:

In the first case sum++ executes 0 + 1 + ... + n-1 times. If you apply arithmetic progression formula, you'll get n (n-1) / 2, which is O(n^2).
In the second case we'll have 0 + 1 + 4 + 9 + ... + (n-1)^2, which is sum of squares of first n-1 numbers, and there's a formula for it: (n-1) n (2n-1)
The last one is interesting. You can see, actually, that the most nested for loop is called only when j is a multiplicand of i, so you can rewrite the program as follows:
int n = 500;
for(int i = 0; i < n; i++) {
   for(int m = 0; m < i; m++) {
       int j = m * i;
       for( k = 0; k < j; k++)
             sum++
   }
}

It's easier to work with math notation:

The formula is derived from the code by analysis: we can see that sum++ gets called j times in the innermost loop, which is called i times, which is called n times. In the end, the problem boils down to a sum of cubes of first n numbers plus lower-order terms (which do not affect the asymptotics)
One final note: it looks obvious, but I'd like to show that in general sum of first N natural numbers in dth power is Ω(N^(d+1)) (see Wikipedia for Big-Omega notation), that is it grows no slower than that function. You can apply the same reasoning to prove that a stronger condition is satisfied, namely, it belongs to Θ(N^(d+1)), which combines both Ω and O.

