计算算法复杂性 - 混淆

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)!