时间复杂度分析——如何简化表达式

Question

我的算法的复杂度有以下表达式。但是我不确定如何进一步简化它以用 Big-O 表示法表示。

   T(n) = 3 * T(n-1) + 3 * T(n-2) + 3 * T(n-3) + ... + 3 *T(1)
   T(1) takes constant time.

感谢任何帮助。

Answer 1

计算T(n-1)，我们得到：

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

如此有效，

T(n) = 3*T(n-1) + T(n-1) = 4*T(n-1) = 4*(4*T(n-2))

因此 T(n) = 4^{(n - 1)}.

Time complexity analysis - how to simplify the expression