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

1.4k Views Asked by At

How is the constant before the $T$ important to the result from $T(n)$

I know that

\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*}

and so i don´t know if the 3 before $T$ from $T(n) = 3T(n-1)$ is an $\theta(3^n)$ or if the constant $3$ isn't important and the result is $\theta(n)$.

1

There are 1 best solutions below

0
On BEST ANSWER

Taking the logarithm and setting $S(n)=\log(T(n))$, the recurrence is

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

Then $$T(n)\to\Theta(\exp(n)),$$ wich grows much faster.