麻烦找到这个循环的大O时间

Question

我正在尝试为以下代码段找到Big O运行时间:

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

由于n的乘法,或者只是O(n ^ 2),我不确定它是否是O(n ^ 3).一些帮助将不胜感激:)

Answer 1

内部循环将执行恰好0 + 1 + ... + n ^ 2 - 2 + n ^ 2 - 1 =(n ^ 2)(n ^ 2 - 1)/ 2次(参见算术系列),所以它实际上是为O(n ^ 4).