Recurrence relation T(n) = 3T(n-1) + n [duplicate]

I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of the recurrence tree, is there a more mathematical way to approach it?

marked as duplicate by Raphael♦Apr 29 '18 at 15:37

Using the substitution method, we find out that \begin{align*} T(n) &= n + 3T(n-1) \\ &= n + 3(n-1) + 3^2T(n-2) \\ &= n + 3(n-1) + 3^2(n-2) + 3^3T(n-3) \\ &= \cdots \\ &= n + 3(n-1) + 3^2(n-2) + \cdots + 3^{n-1}(n-(n-1)) + 3^n T(0) \\ &= \frac{3^{n+1}-2n-3}{4} + 3^nT(0) \\ &= \Theta(3^n). \end{align*} Even without doing the full calculation it is not hard to check that $T(n) \geq 3^{n-1} + 3^n T(0)$, and so $T(n) = \Omega(3^n)$. A cheap way to obtain the corresponding upper bound is by considering $S(n) = T(n)/3^n$, which satisfies the recurrence relation $S(n) = S(n-1) + n/3^n$. Repeated substitution then gives $$\frac{T(n)}{3^n} =\sum_{m=1}^n \frac{m}{3^m} + T(0).$$ Since the infinite series $\sum_{m=1}^\infty \frac{m}{3^m}$ converges, this implies that $\frac{T(n)}{3^n} = \Theta(1)$ and so $T(n) = \Theta(3^n)$.