运行嵌套循环的时间

Question

对不起,如果已经提出这个问题,我不知道如何搜索它.

假设你有以下循环

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

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

Answer 1

外循环的运行时(单独)是O(n),内循环的运行时是O(ni).因此循环的时间将是(n)(ni),当你丢弃常量i时,运行时将是O(n ^ 2).