algorithm - 计算算法复杂度 - 困惑

Question

我有以下代码片段:

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

复杂度为 O(n^2)，但如果我想深入了解内部循环的复杂度，那么它会是 (n (n-1))/2 或 (n-1)!?

Answer 1

是的，O(n^2)，但实际上 0+1+...+n-1=n(n-1)/2 = O(n^2)，绝对不是 (n-1)!