Анализ сложности времени - как упростить выражение

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

Вычисление Т (п-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)) 

Таким образом Т (п) = 4 ^{(п - 1)}.