algorithm - T(n-1)的时间复杂度

我对解决这个时间复杂性问题感到困惑。

T(n) = T(n-1)

我知道在快速排序的最坏情况下T(n) = T(n-1) + T(1) + n
其计算结果为(n-1) + (n-2) + (n-3) + ... + 1&此几何序列等于O(n^2)
然而。我看到stackoverflow上的答案是T(n) = T(n-1) + c = O(n)。
如果这也等于(n-1) + (n-2) + (n-3) + ... + 1，也等于O(n^2)，这怎么可能呢？
有人能解释一下吗？

最佳答案

T(n) = T(n-1) + c不等于(n-1) + (n-2) + (n-3) + ... + 1，因为要添加的项是常量基本上：
不添加任何内容：

T(n) = T(n-1)
0 + 0 + 0 + ... + 0 = 0
O(1)

添加常数：

T(n) = T(n-1) + c
c + c + c + ... + c = nc
O(n)

添加变量：

T(n) = T(n-1) + n
1 + 2 + 3 + ... + n = n(n+1)/2
O(n^2)

关于algorithm - T(n-1)的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23667395/