質問: O(k*N^2)kがNと同じと考えられる場合O(N^3)のようにまとめることは出来ますか? 例えばNxNの行列とN次元ベクトルの掛け算の場合O(N^2)となりますが N回行った場合O(N^3)のようにまとめてもいいのですか?
回答: k=cN+e(N) (cは定数、e(x)はxの1次未満の項からなる式、例えばlog(N)とか) と表せる関係があるなら、もちろんO(k*N^2)はO(N^3)です。