runtime - 双嵌套的大 Theta 运行时间

Question

我试图在双嵌套 for 循环上确定 Big Theta 运行时间，这比常规的 Θ(n ² ) 双循环要花哨一些。

for i=0..n do
    for j=0..i do
        // some O(1) work
    end
end

我知道我可以说它是 O(n ² )，但我喜欢 Θ 格式。

Answer 1

两个嵌套循环的步数：

1 + 2 + ... + (n+1) = (n+1)*(n+2)/2

为了证明运行时间是 Θ(n ² )，你需要找到三个常数c1，c2这样n0：

c1 * n ² <= (n+1)*(n+2)/2 <= c2 * n ²

对于所有人n >= n0。

既然你知道现在要做的具体任务，这里是我的提示：

c1和c2可以选择为1/2和1分别找到一个合适的n0.