T(n)= T(n-1) + n 总是 n(n+1)/2 还是 O(n^2)

Question

我看了一个视频，他们证明了 T(n)= T(n-1) + n is O(n^2)

我有以下表达式：

T(1) = 4 
T(N) = T(N – 1) + N + 3, N > 1 

我的问题是，上面的表达式是否以相同的方式解决，即使 N 后面有一个 +3。

问题有点乱，但我希望你明白了。如果有问题我会尽量解释的更好

一句话就是T(N) = T(N – 1) + N + 3 = O(n^2)

Answer 1

T(n) = T(n-1) + n-1 + 4 => 通过加 1 和减 1 给出方程

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

现在，T(1) = 常数。

因此，从 eq(1),

T(n) = T(n-1) + (n-1) ...(2)

Eq(2) 减少到 T(n) = T(n-k) + n*k - k*(k+1)/2 ...(3)

在等式(3),

我们得到，

T(n) = T(1) + n*(n-1) - (n-1)(n)/2

T(n) = n*(n-1)/2 => O(n^2)

PS: 如果我们不忽略 eq(1) 中的 T(1)，最终方程我们get 是 T(n) = n*(n-1)/2 + T(1) + 4*k => T(n) = n*(n-1)/2 + 4 + 4*(n-1) 仍然给出 O(n^2) 作为最终答案。