三个嵌套for循环的渐近分析

Question

我想计算这个嵌套for循环的θ复杂度:

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

我会说它是n ^ 3,但我不认为这是正确的,因为每个for循环不会从1变为n.我做了一些测试:

n = 5 - > 10

10 - > 120

30 - > 4060

50 - > 19600

所以它必须在n ^ 2和n ^ 3之间.我尝试了总和公式等,但我的结果太高了.虽然n ^ 2 log(n),但那也错了......

Answer 1

这是O(N^3)。确切的公式是(N*(N+1)*(N+2))/6