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

Question

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

    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

使用 Sigma Notation 是一种有效的循序渐进的方法: