algorithm - What is the complexity of this nested triple for loop?

Question

I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is O(n2). However with the nested addition of the k-loop, I am confused as why the complexity becomes O(n3). Can someone help me understand this?

From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations n*(n+1)/2 which is O(n2).

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

EDIT: Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:

From the counters, it can therefore be seen that: i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity O(n2). A pattern for K was hard to spot but it is known that K depends on J, therefore:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 giving a complexity of O(n3)

I hope this will help people in the future.

EDIT2: thanks Dukeling for the formatting :) Also found a mistake in the last line, corrected now

Answer 1

If you're accustomed to Sigma Notation, here is a formal way to deduce the time complexity of your algorithm (the plain nested loops, precisely):

NB: the formula simplifications might contain errors. If you detect anything, please let me know.