time-complexity - 嵌套循环的运行时间

Question

对不起，如果这个问题已经被问到，我不知道如何搜索它。

假设你有以下循环

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

这是 O(n^2) 还是 O(nlog(n))，为什么？

Answer 1

外循环的运行时间(本身)是 O(n)，内循环的运行时间是 O(n-i)。所以循环的时间是 (n)(n-i)，当你扔掉常量 i 时，运行时间是 O(n^2)。