Show that if $f(2n) \le Cf(n)$ for large enough $n$, where $f:N \to N$. Then $f(n)$ is bounded by a polynomial?
Some suggestions? I tried using the Master theorem but I didn't get some convincent.
Asked
Active
Viewed 35 times
0
prachu
- 1
- 1
-
I assume that you mean "then $f(n)$ is bounded by a polynomial." The single variable $n$ is already bounded by a polynomial, since it is one. :) – John Hughes Jul 19 '17 at 20:24
-
Yes, I already fixed it – prachu Jul 20 '17 at 16:55
-
OK. You fixed it. Now it's just false (as Robert Israel's example shows). Sigh. – John Hughes Jul 20 '17 at 17:00
-
But, for this function there is not a C satisficing the condition. – prachu Jul 20 '17 at 17:04
-
Sure there is: it's $C = 1$. Because $f(2n)$ will always be $f$ applied to an even number, and for every even number $2n$, $f(2n) = 1 \le C f(n)$, since $C = 1$ and $f(n)$ is at least $1$. – John Hughes Jul 20 '17 at 17:31
-
@Raffaele: what does $n/2$ mean when $n$ is an odd integer? (Notice that $f$ is defined to be from $N$ to $N$.) – John Hughes Jul 20 '17 at 17:32
