# 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?

• Do a "repeat by substituion", find the pattern, and finally prove that with induction. – Wen Apr 29 '18 at 15:02
• You were very, very careless with your proposed solution. – gnasher729 Apr 29 '18 at 15:05
• @gnasher729 that's not a super helpful comment! maybe tell me where I went wrong since I made a genuine effort and am confused by the material? – zipzip12 Apr 29 '18 at 16:25
• Ok, assume T(0) = 1, take a spreadsheet, calculate T(1) to T(50) and compare with n^3. – gnasher729 Apr 29 '18 at 17:17
• "Careless" because you just need to swap two letters to make it correct. – gnasher729 Apr 30 '18 at 6:14

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)$.