嵌套循环的运行时间(Big O)

Question

这个算法的运行时间是多少:

for i=1 to n^2
    for j=1 to i
        // some constant time operation

我想说O(n ^ 4)但我不能确定.你怎么知道这个？

Answer 1

n ^ 4是正确的.内循环运行平均为(n ^ 2)/ 2时间,因为i线性上升到n ^ 2,并且运行(n ^ 2)次.