Mathematical derivation of O(n3) complexity for general three nested loops : http://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop goes into the mathematical derivation through summation of two loops O(n2) complexity.

I tried an exercise to derive how i can get O(n3) for the following examples of three nested loops.
Simple three nested loops. 
--
       for (int i = 1; i < n; i++)
            for (int j = 1; j < n; j++)
                for (int k = 1; k < n; k++)
                     print(i * k * j);



Summation is
= (n + n + n + .... + n) + (n + n + n + ... + n) + ... + (n + n + n + ... + n)

= n2 + n2 + .... + n2

n times n2 = O(n3)

Three nested loops not run n times from beginning
---

     for(int i = 1; i < n; i++)
         for(int j = i; j < n; j++)
             for(int k = j; k < n; k++)
                 print(i *j * k)

The above is a pretty common form of nested loops and i believe the summation would be something as follows

= (n + (n -1) + (n -2) + (n - 3) + ... + 1) 
+ ((n -1) + (n - 2) + (n - 3) +... + 1) 
+ ((n -2) + (n -3) + (n - 4) + ... + 1) 
+ ... 
+ ((n - (n -2)) + 1)


= n(n - 1) /2 + (n-1) (n -2) / 2 + (n-2)(n-3)/2 + .... + 1

=
*From here i am slightly not sure if my logic is correct . I believe
each of the above evaluate to a polynomial whose greatest value is n2 and as thats what we care about in time complexity, the above equation breaks down to.*

= n2 + n2 + n2 +... +n2

= which is n times n2 = O(n3).

Is my assumption correct?

Three nested loops not run n times from end
--

    for(int i = 1; i < n; i++)
         for(int j = 1; j < i; j++)
             for(int k = 1; k < j; k++)
                 print(i *j * k)

If the above was a two nested loop the summation would have been 1 + 2 + 3 + 4 + ... + n. However, for the three nested occurence i am deducing it to be

= 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3) + (1 + 2 + 3 + .... + n)

From here i am not sure how to derive O(n3) or how the above summation would be further simplified.
