如何解决以下递归并找到 Theta 界限

Question

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

其中 c 是常数

Answer 1

如果展开递归，对于第一种情况，您将得到：

1^c + 2^c + ... + (n-1)^c + n^c

这是一个Faulhaber's formula。它告诉你复杂度是 O(n^(c+1))

第二个是：

c^1 + c^2 + ... + c^(n-1) + c^n

哪个是sum of geometrics和O(c^n)