Timeline for Complexity analysis on a parameterized recurrence relation
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2015 at 7:53 | vote | accept | Leo | ||
| Apr 30, 2015 at 7:53 | comment | added | Leo | 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! | |
| Apr 29, 2015 at 16:05 | comment | added | Emil Jeřábek | ... 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. | |
| Apr 29, 2015 at 16:01 | comment | added | Emil Jeřábek | ... 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 ... | |
| Apr 29, 2015 at 15:56 | comment | added | Emil Jeřábek | 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 ... | |
| Apr 29, 2015 at 15:37 | comment | added | Leo | 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! | |
| Apr 29, 2015 at 11:35 | comment | added | Emil Jeřábek | 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. | |
| Apr 29, 2015 at 11:26 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
fix off-by-one errors
|
| Apr 27, 2015 at 14:10 | comment | added | Leo | 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. | |
| Apr 25, 2015 at 17:06 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |