このアルゴリズム（n^2）*（n^2 + 1）/ 2（つまりO（n/4））の実行時間はなぜですか？

Question

だから、私のインストラクターが私たちを与えた質問は、私たちは、このアルゴリズムの実行時間見つけました：溶液中では

{n > 0} 
    i := 1; 
    while i ≤ n^2 
    j := 1; 
    while j ≤ i 
     j := j + 1; 
    endwhile 
    i := i + 1; 
endwhile 

を、ランタイムはここ のn^2（N^2 + 1）/ 2、ですΘ（n^4）です。

したがって、最初のwhileループのランタイムはn^2ですが、なぜ2番目のループの実行時間は（n^2 + 1）/ 2になりますか？

ご協力いただきありがとうございます。

Answer 1

第2ループはi回実行されます。

iが1からn^2まで変化するのであれば、実行時には、あなたがn^2でkを交換する場合

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

だから、あなたがn^2*(n^2+1)でランタイムを入手することになりました

1 + 2 + 3 + ... + n^2 

注意です。 私は正しいidentがあったとします：

{n > 0} 
    i := 1; 
    while i ≤ n*n 
     j := 1; 
     while j ≤ i 
     j := j + 1; 
     endwhile 
     i := i + 1; 
endwhile