<p>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.</p>

<p>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$.</p>

<p>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.</p>

<p>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}).$$</p>

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

CC BY-SA 3.0
2015-04-27T14:10:10.160Z
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
CC BY-SA 3.0
2015-04-29T11:35:46.510Z
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
CC BY-SA 3.0
2015-04-29T15:37:03.823Z
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
CC BY-SA 3.0
2015-04-29T15:56:11.330Z
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
CC BY-SA 3.0
2015-04-29T16:01:52.397Z
... 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
CC BY-SA 3.0
2015-04-29T16:05:21.363Z
... this for a while reveals that the negative terms in the recurrence are a pain in the ass, and one would like to get rid of them. Now, this is the point to make a guess: the recurrence is supposed to grow like $\phi^{2n}$, and $\phi^n$ is the growth rate of the recurrence $f(n)=f(n-1)+f(n-2)$ which conveniently has no negative terms, so maybe one could complete $T(n)$ with half-steps to something of a similar form. This leads to the $S(n)$ recurrence, and then the proof becomes fairly routine.
Emil Jeřábek
CC BY-SA 3.0
2015-04-30T07:53:18.800Z
Thank you for sharing the complete reasoning, it's very instructive. I often only think to find the answer by an exact way instead of performing a careful analysis to "guess" the result then prove it, while now I feel that the latter may be much powerful in many cases!
Leo
CC BY-SA 3.0
2015-04-25T17:06:33.200Z
2015-04-29T11:26:27.310Z
2015-04-29T11:26:27.310Z
Emil Jeřábek
<p>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!</p>

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

<p>In general, for recurrence like</p>

<p>$$
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:</p>

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

<p>Let the result be $a_n=Ad^n$</p>

<h3>2. Find a particular solution of the non-homogeneous recurrence</h3>

<p>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$.</p>

<p>More general forms for common $f(x)$ (extracted from the book referenced at last):
<img src="https://i.sstatic.net/P7Tgd.png" alt="Particular solutions for common $f(x)$"></p>

<h3>3. Just add up the two solutions</h3>

<p>$a_n=Ad^n+Bc^n$</p>

<h3>4. Finally, use initial values to determine A.</h3>

<hr>

<h3>Application to our problem</h3>

<p>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 <em>Non-homogeneous recurrence</em> 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.</p>

<p>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)$$</p>

<p>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.</p>

<p>I hope that the idea is clear, please help me to make it more formal. I refer readers to the book <a href="http://www.amazon.fr/Applied-Combinatorics-Alan-Tucker/dp/0470458380" rel="nofollow noreferrer">Applied-Combinatorics-Alan-Tucker</a>.More references can be found by searching "solve linear non-homogeneous recurrence".</p>

<hr>

<p>UPDATE 1:
In fact since $\alpha^{1-\beta}&lt;\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...</p>

CC BY-SA 3.0
2015-05-04T09:35:09.383Z
2015-05-04T09:43:45.147Z
2015-05-04T09:43:45.147Z
Leo
<p>In order to analyse the complexity of our algorithm, we try to solve this recurrence:</p>

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

<p>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$. </p>

<p>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$.</p>

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

<p>Thank you in advance for any idea.</p>

<p>UPDATE 1:</p>

<ol>
<li><p>The recurrence has been corrected, and yes, $\alpha$ should be between 2 and 3.</p></li>
<li><p>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)}$</p></li>
</ol>

<p>UPDATE 2:</p>

<p>To somewhat simply the problem, we may consider $g(n)=\beta n$ and try to find the $\beta$ ?</p>

CC BY-SA 3.0
2015-04-24T09:24:04.893Z
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
CC BY-SA 3.0
2015-04-24T14:06:16.243Z
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
CC BY-SA 3.0
2015-04-25T08:54:06.260Z
@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
<analysis-of-algorithms><complexity>
Complexity analysis on a parameterized recurrence relation
Leo
# Complexity analysis on a parameterized recurrence relation

(Asked by: username_0 on 2015-04-24)

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

**Tags:** analysis-of-algorithms, complexity

> **Comments:**
> **username_1**: 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$.  
> **username_2**: 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$.  
> **username_3**: @username_2: 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.  

---

## 2 answers

### Answer by username_3 on 2015-04-25. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: 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!  
> **username_3**: 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 ...  
> **username_3**: ... 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 ...  
> **username_3**: ... this for a while reveals that the negative terms in the recurrence are a pain in the ass, and one would like to get rid of them. Now, this is the point to make a guess: the recurrence is supposed to grow like $\phi^{2n}$, and $\phi^n$ is the growth rate of the recurrence $f(n)=f(n-1)+f(n-2)$ which conveniently has no negative terms, so maybe one could complete $T(n)$ with half-steps to something of a similar form. This leads to the $S(n)$ recurrence, and then the proof becomes fairly routine.  
> **username_0**: Thank you for sharing the complete reasoning, it's very instructive. I often only think to find the answer by an exact way instead of performing a careful analysis to "guess" the result then prove it, while now I feel that the latter may be much powerful in many cases!  

---

### Answer by username_0 on 2015-05-04. Score: 0

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):
![Particular solutions for common $f(x)$](https://i.sstatic.net/P7Tgd.png)

### 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](http://www.amazon.fr/Applied-Combinatorics-Alan-Tucker/dp/0470458380).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...


---

