嵌套for循环的大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)).