Recurrence relation T(n) = 3T(n-1) + n
Using the substitution method, we find out that
$$
\begin{align*}
T(n) &amp;= n + 3T(n-1) \\ &amp;=
n + 3(n-1) + 3^2T(n-2) \\ &amp;=
n + 3(n-1) + 3^2(n-2) + 3^3T(n-3) \\ &amp;= \cdots \\ &amp;=
n + 3(n-1) + 3^2(n-2) + \cdots + 3^{n-1}(n-(n-1)) + 3^n T(0) \\ &amp;=
\frac{3^{n+1}-2n-3}{4} + 3^nT(0) \\ &amp;= \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)$.