このコードフラグメントの最悪の場合の分析は何ですか？

Question

sum = 0; 
for (int i = 0; i < N; i++) 
    for(int j = 0; j < i*i; j++) 
    sum++; 

私の答えは完全にはわかりません。私は内側のループがi^2の演算を実行し、外側のループがN回実行されると思いますので、最終的な答えはO（N^3）でしょうか？

Answer 1

操作回数はsum = 1 + 4 + 9 + ... + N^2です。これは、i = 0の場合、jが0回増分するためです。 i = 1の場合、jは1回インクリメントします。 i = 2の場合、jはそれ自身をインクリメントします4回、などとなります。

この合計はN(N + 1)(2N + 1)/6に等しいので、アルゴリズムは実際にO(N^3)です。誘導によってこの式をproveすることができます。

Answer 2

それは私には似ています（漸近的に）。