Complexity analysis on a parameterized recurrence relation

Question

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:

1. The recurrence has been corrected, and yes, $\alpha$ should be between 2 and 3.

2. 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$ ?

Answer 1

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)>T(n)$ for all $n>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)&\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&\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)&\text{$n$ even,}\\ S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)+1)/2}&\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>0$, where $$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$ and consequently $$T(n)=O(\phi^{2n}).$$

Pick $n_0>2$, $a,b>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)&\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}\\ &=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{(d+1)/2})\psi^n\\ &\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>\phi^{-c}.$$

Answer 2

Just to make the discussion more complete, I'd like to add another approach to solve this problem. Please do not hesitate to give your comments/corrections!

I've just found in the literature some standard ways to solve Non-homogeneous Recurrence, which is exactly our case if we don't consider the parameter $k$.

In general, for recurrence like

$$ a_n=b_1a_{n-1}+b_2a_{n-2}+...+b_ka_{n-k}+f(n) $$ where $f(n)$ is a function on $n$, here are the steps to follow:

1. Solve the Associated Homogeneous Recurrence (which can be gotten by replace $f(n)$ with 0) in general form

Let the result be $a_n=Ad^n$

2. Find a particular solution of the non-homogeneous recurrence

We can guess the form of solution according to the form of $f(n)$, e.x. if $f(x)=c^n$, then we know the form of the particular solution is $a^*_n=Bc^n$. Then we plug it into the original recurrence to get the value of $B$.

More general forms for common $f(x)$ (extracted from the book referenced at last):

3. Just add up the two solutions

$a_n=Ad^n+Bc^n$

4. Finally, use initial values to determine A.

---

Application to our problem

Now let's try to apply this to solve our problem. Note $\alpha$ the exponential base that we are searching for, i.e. $T(n)=O^*(\alpha^n)$, by $*$ we suppress polynomial multiplicative terms. Now by taking $k=\beta n$, we rewrite our recurrence as: $$ T(n)=3T(n-1)-T(n-2)+ (\alpha^{1-\beta})^n+ (3^\beta)^n $$ which is just a Non-homogeneous recurrence as above. Now we can solve the homogeneous part to get its complexity, which is $O^*( (\phi^2)^n)$, where $\phi= \frac{1+\sqrt{5}}{2}$ is the golden ratio.

Since we only want an asymptotic complexity, the steps followed are much simplified: we know directly that $$ \alpha=max(\phi^2, \alpha^{1-\beta}, 3^\beta)$$

Therefore $\alpha\geq \phi^2$, so we only need to let $$\alpha^{1-\beta}= 3^\beta$$ and set $\alpha= \phi^2$ to get $\beta$, which is $0.467$, same as the accepted answer.

I hope that the idea is clear, please help me to make it more formal. I refer readers to the book Applied-Combinatorics-Alan-Tucker.More references can be found by searching "solve linear non-homogeneous recurrence".

---

UPDATE 1: In fact since $\alpha^{1-\beta}<\alpha$, so we only need to assure $3^\beta \leq \phi^2$, which gives $$\beta \leq 0.876$$. However I still prefer to take $\beta=0.467$ since in this way the order of terms that we suppress is smallest...