1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – R B Apr 24 '15 at 9:24
  • 2
    $\begingroup$ 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$. $\endgroup$ – Aravind Apr 24 '15 at 14:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Apr 25 '15 at 8:54
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Leo Apr 27 '15 at 14:10
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 29 '15 at 11:35
  • $\begingroup$ 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! $\endgroup$ – Leo Apr 29 '15 at 15:37
  • $\begingroup$ 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 ... $\endgroup$ – Emil Jeřábek Apr 29 '15 at 15:56
  • $\begingroup$ ... 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 ... $\endgroup$ – Emil Jeřábek Apr 29 '15 at 16:01
0
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.