Big-O complexity of nested for loops

Question

I'm confused about the complexity of the following (the operation performed inside the inner loop is in constant time):

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

is this O(n^2) or O(n)? I figure O(n^2). Any ideas?

also the following makes me curious:

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).