big-o - ネストされた for ループの非常に複雑な問題

Question

次の複雑さについて混乱しています（内側のループ内で実行される操作は一定時間です）：

for(int i=0; i<n; i++)
  for(int j=i; j<n; j++)

これは O(n^2) ですか、それとも O(n) ですか? 私は O(n^2) を計算します。何か案は？

また、次のことも興味があります。

for(int i=0; i<n; i++)
   for(j=0; j<i; j++)

Answer 1

Definitely O(n squared), of course. Summary explanation for both cases: 1 + 2 + ... + n is n(n+1)/2, that is, (n squared plus n) / 2 (and in big-O we drop the second, lesser part, so we're left with n squared / 2 which is of course O(n squared)).

Answer 2

You are correct, those nested loops are still O(n^2). The actual number of operations is something close to (n^2)/2, which, after discarding the constant 1/2 factor, is O(n^2).