complexity-theory - ネストされた 3 つの 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