1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do a "repeat by substituion", find the pattern, and finally prove that with induction. $\endgroup$ – Wen Apr 29 '18 at 15:02
  • $\begingroup$ You were very, very careless with your proposed solution. $\endgroup$ – gnasher729 Apr 29 '18 at 15:05
  • $\begingroup$ @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? $\endgroup$ – zipzip12 Apr 29 '18 at 16:25
  • $\begingroup$ Ok, assume T(0) = 1, take a spreadsheet, calculate T(1) to T(50) and compare with n^3. $\endgroup$ – gnasher729 Apr 29 '18 at 17:17
  • $\begingroup$ "Careless" because you just need to swap two letters to make it correct. $\endgroup$ – gnasher729 Apr 30 '18 at 6:14
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.