My professor told me that the following recurrence relation has linear complexity, but I'm not sure.
$T(n) = 3 T(n-1)+5$: \begin{equation} \begin{split} T(n) & = 3 T(n-1)+5 \Rightarrow \\ T(n-1) & = 3T(n-2) +5 \Rightarrow \\ T(n)-T(n-1) & = 3T(n-1)-3T(n-2) \Rightarrow\\ T(n) & = 4T(n-1)-3T(n-2) \Rightarrow \\ q^2 & = 4q - 3 \Rightarrow \\ q_{1,2} &= 3, 1 \Rightarrow\\ T(n) &= \alpha 1^n + \beta 3^n \end{split} \end{equation}
From these $T(0)=0, T(1)=5$ $\Rightarrow$ $\alpha=-5/2$ and $\beta=5/2$ $\Rightarrow$ $T(n) = \frac{-5}{2} +\frac{5}{2}3^n = O(3^n)$
How can be this linear? What am I missing?
what your professor meant: the amount of calculations required to calculate $T(n)$ is linear in $n$ (most recurrences are).
what you did is calculating a closed form (or it seems to be an approximation) of $T(n)$ for a specific $n$.