big-o - 无法找到此循环的大 O 时间

Question

我正在尝试查找以下代码片段的 Big O 运行时间:

for( i = 0; i < n * n; i++ )
    for( j = 0; j < i; j++ )
        k++;

由于 n 的乘法，我不确定它是 O(n^3)，还是 O(n^2)。一些帮助将不胜感激:)

Answer 1

内循环将执行 0 + 1 + ... + n^2 - 2 + n^2 - 1 = (n^2)(n^2 - 1)/2 次(见 Arithmetic Series )，所以它是实际上是 O(n^4)。