algorithm - Big Theta 表示法的渐近运行时间

Question

考虑到以下算法，

Loop1 until(i<n^2)
     Loop2 until(j<i^2)
        ....
        j=j+4
     End Loop2
     i=i*3
End Loop1

我认为这是Theta(n^2*log(n))。这是正确的还是 Big Theta 比这更高？

Answer 1

不，这是不正确的。

让 i 在 n^2 附近，当 n^2 是 3 的某个幂时就是这种情况。然后 j 的内部循环将运行 i^2 / 4 = Theta(n^4) 步。所以总运行时间不能小于 Theta(n^4)。

提示：这恰好是最后的总运行时间，你明白为什么吗？