Resolver $T(n) = 3T(n-1)$

Question

¿Cómo es la constante antes del $T$ importante para el resultado de $T(n)$

Sé que

\begin{equation*} T(n) = T(n-1) + 3 \Rightarrow \theta(n)~\text{and}~T(n) = T(n-1) + n \Rightarrow \theta(n^2) \end{equation*}

y por eso no se si los 3 anteriores $T$ de $T(n) = 3T(n-1)$ es un $\theta(3^n)$ o si la constante $3$ no es importante y el resultado es $\theta(n)$ .

Answer 1

Tomando el logaritmo y fijando $S(n)=\log(T(n))$ la recurrencia es

$$S(n)=S(n-1)+\log(3)\to\Theta(n).$$

Entonces $$T(n)\to\Theta(\exp(n)),$$ que crece mucho más rápido.