時間複雜度分析 - 如何簡化表達式

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）}。