# 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:

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

• It seems that no matter which $k$ you choose you'll end up with $T(n)=2^{\Theta(n)}$, probably somewhere between $2^n$ and $3^n$. – R B Apr 24 '15 at 9:24
• The generating function for $T(n)$ depends only on $k$ and not on $n$; it should be a rational function rather than a polynomial in this case; the optimal value of $k$ depends only on this rational function and is not a function of $n$. – Aravind Apr 24 '15 at 14:06
• @Aravind: That's just not true. You seem to start from the assumption that $k$ is constant, and derive that the optimal $k$ is constant, but that's circular reasoning. For constant $k$, the recurrence grows as $O(\alpha_k^n)$ for certain constants $\alpha_k$ that decrease towards $1+\phi$ as $k$ increases. From this, it's clear that the optimal choice of $k=g(n)$ must be an unbounded function. – Emil Jeřábek Apr 25 '15 at 8:54

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}.$$

• I've really enjoyed reading your analysis which is beautiful for me, especially for the establishment of $S(n)$. As a learner, I would like to know where can I find more resources about this kind of recurrence analysis? A little problem to be verified is that in (**), the term 3(k′(n)−1)/2 may be 3(k′(n)+1)/2 and k′(n) may be 2k((n+1)/2)−1, in order to establish the recurrence. But of course this does not affect much the result. – Leo Apr 27 '15 at 14:10
• Thanks for the correction. I’m afraid I don’t really know where to point you to. You seem to know the usual theory of linear recurrences with constant coefficients. I am not aware of any general theory of that sort for recurrences like here where the degree is variable; you have to improvise. – Emil Jeřábek Apr 29 '15 at 11:35
• I'll need much more experience to improvise :). Anyway I'll try to guess $S(n)$ like you did for this kind of recurrences. Thanks for your help! – Leo Apr 29 '15 at 15:37
• So, introducing the $S(n)$ ansatz at the beginning shortens the proof in the final polished answer, but you’re not really supposed to guess it just like that. A more didactic approach is as follows. First, assuming the recurrence is not too bad-behaved, dropping the $T(n-k)$ term should give a lower bound on $T(n)$, and the theory of linear recurrences shows that it grows like $\phi^{2n}$. On the other hand, if we fix $k$ as constant, we get a recurrence of growth $\alpha_k^n$, where $\alpha_k$ are roots of the appropriate polynomials, and it is easy to figure out that $\alpha_k$ decrease ... – Emil Jeřábek Apr 29 '15 at 15:56
• ... towards $\phi^2$. So, the optimal setting should have $k$ an unbounded function, and it should result in $T(n)=(\phi^2+o(1))^n$. At this point, we can guess the right $k$ by minimizing $T(n-k)+3^k\sim \phi^{2(n-k)}+3^k$, giving $k\sim\beta n$ with $\beta$ as in the answer. With this setting, the $T(n-k)+3^k$ term is exponential in $n$ with a base smaller than $\phi^2$, hence one should expect all these extra terms to sum to something negligible compared to the main $\phi^{2n}$ part, hence we should expect $T(n)=O(\phi^{2n})$. Now, the problem is how to prove that formally. Playing with ... – Emil Jeřábek Apr 29 '15 at 16:01

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$

### 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...