Complexity analysis on a parameterized recurrence relation In order to analyse the complexity of our algorithm, we try to solve this recurrence:

$T(n)=3T(n-1)-T(n-2)+T(n-k)+3^k$ ; in which $k$ is a parameter to be fixed. 

We know that this kind of recurrence means $T(n)=O(\alpha^n)$, where $\alpha$ is the zero root of the equation $f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-k}-3^k$. 

The term $3^k$ expects a small value of $k$, while the rest terms want a big value of $k$, therefore we believe that there should be a best choice of $k$.

So the question is how to choose $k$, $(k=g(n))$ in order to minimize $\alpha$?

Thank you in advance for any idea.

UPDATE 1:


The recurrence has been corrected, and yes, $\alpha$ should be between 2 and 3.
Please note that $k$ is a dynamic value, which changes during the recursion. So it's better to consider the recurrence as $T(n)=3T(n-1)-T(n-2)+T(n-g(n))+3^{g(n)}$


UPDATE 2:

To somewhat simply the problem, we may consider $g(n)=\beta n$ and try to find the $\beta$ ?
First, if $k(n)$ and $T(n)$ are non-negative functions satisfying
$$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$
for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)&gt;T(n)$ for all $n&gt;n_0$ by induction on $n$. Thus, $T$ is eventually increasing.

Second, proving bounds on $T(n)$ is inconvenienced by the presence of a negative term in $(*)$. We can fix this by defining a new function
$$S(n)=\begin{cases}T(\tfrac n2)&amp;\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&amp;\text{$n$ odd,}\end{cases}$$
which (as we just proved) is also eventually nonnegative, and satisfies the recurrence
$$S(n)=\begin{cases}S(n-1)+S(n-2)&amp;\text{$n$ even,}\\
S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)+1)/2}&amp;\text{$n$ odd,}\end{cases}\tag{${*}{*}$}$$
where $k'(n)=2k((n+1)/2)-1$.

This makes it obvious that
$$S(n)\ge S(n-1)+S(n-2),\qquad n\gg0,$$
hence
$$S(n)=\Omega(\phi^n)\quad\text{and}\quad T(n)=\Omega(\phi^{2n}),$$
where $\phi=(1+\sqrt5)/2\approx1{.}618$ is the golden ratio.

I claim that a suitable choice of $k(n)$ gives a matching upper bound. The right choice is to make the two terms involving $k'$ approximately equal; since we are shooting for $S(n)\approx\phi^n$, this means
$$\phi^{n-k'(n)}\approx3^{k'(n)/2},$$
thus
$$k'(n)\sim\beta n,\qquad\beta=\frac{2\log\phi}{2\log\phi+\log3}\approx0{.}467$$
and $k(n)\sim\beta n$ as well. So, let us assume
$$\beta n+c\le k'(n)\le\beta n+d$$
for some constants $c,d$ (with some conditions on $c$ below). I claim that with this setting, any nonnegative solution of $({*}{*})$ satisfies
$$S(n)\le a\phi^n-b\psi^n\tag{${*}{*}{*}$}$$
for some constants $a,b&gt;0$, where
$$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$
and consequently
$$T(n)=O(\phi^{2n}).$$

Pick $n_0&gt;2$, $a,b&gt;0$ such that $({*}{*})$ holds for $n\ge n_0$, and $({*}{*}{*})$ holds for $n\le n_0$ (there will be one more condition below). We want to show $({*}{*}{*})$ for all $n$ by induction. The induction step goes as follows:
$$\begin{align*}
S(n)&amp;\le a(\phi^{n-1}+\phi^{n-2})-b(\psi^{n-1}+\psi^{n-2})+a\phi^{(1-\beta)n-c}+3^{(\beta n+d+1)/2}\\
&amp;=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{(d+1)/2})\psi^n\\
&amp;\le a\phi^n-b\psi^n.
\end{align*}$$
The last step is valid if
$$b(\psi^{-2}+\psi^{-1}-1)\ge a\phi^{-c}+3^{(d+1)/2}.\tag{${*}{*}{*}{*}$}$$
We can arrange this condition by observing that the other requirements on $a,b$ continue to hold if we increase both by the same amount; this will eventually make $({*}{*}{*}{*})$ true if $c$ is sufficiently large so that
$$\psi^{-2}+\psi^{-1}-1&gt;\phi^{-c}.$$