嵌套for循环的Big-O复杂性

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

当然是O(n squared)。两种情况的摘要说明:1 + 2 + ... + n是n(n+1)/2，即(n squared plus n) / 2(在big-O中，我们删除了第二个小部分，因此我们剩下n平方/2，这当然是O(n squared))。