Asymptotic analysis of three nested for loops

问题:

I want to calculate the theta complexity of this nested for loop:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                // statement

I'd say it's n^3, but I don't think this is correct, because each for loop does not go from 1 to n. I did some tests:

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

So it must be between n^2 and n^3. I tried the summation formula and such, but my results are way too high. Though of n^2 log(n), but that's also wrong...

回答1:

It is O(N^3). The exact formula is (N*(N+1)*(N+2))/6

回答2:

Using Sigma Notation is an efficient step by step methodology: