Timeline for Complexity analysis on a parameterized recurrence relation

10 events

when toggle format	what		by	license	comment
May 4, 2015 at 9:35	answer	added	Leo		timeline score: 0
Apr 30, 2015 at 7:53	vote	accept	Leo
Apr 25, 2015 at 17:06	answer	added	Emil Jeřábek		timeline score: 4
Apr 25, 2015 at 8:54	comment	added	Emil Jeřábek		@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.
Apr 24, 2015 at 14:06	comment	added	Aravind		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$.
Apr 24, 2015 at 10:20	history	edited	Leo	CC BY-SA 3.0	Add an idea of simplification
Apr 24, 2015 at 10:10	history	edited	Leo	CC BY-SA 3.0	Recurrence formula updated.
Apr 24, 2015 at 9:24	comment	added	R B		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$.
Apr 24, 2015 at 8:56	review	First posts
Apr 27, 2015 at 10:16
Apr 24, 2015 at 8:51	history	asked	Leo	CC BY-SA 3.0