runtime - 二重ネストされた For での Big Theta 実行時間

Question

^{私は、通常の Θ(n 2} ) 二重ループよりも少し手の込んだ二重ネストされた for ループで Big Theta ランタイムを突き止めようとしています。

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

^{O(n 2} )と言えるのは分かっていますが、Θ形式でお願いします。

Answer 1

2つのネストされたループのステップ数：

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

実行時間がΘ（n2）であることを証明するには^、c1次の3つの定数を見つける必要がありc2ますn0。

c1 * n ² <=（n + 1）*（n + 2）/ 2 <= c2 * n ²

すべてのためにn >= n0。

あなたは今やるべき特定の仕事を知っているので、ここに私のヒントがあります：

c1としてc2選択することができ1/2、1それぞれ、適切なを見つけますn0。