Does there exist a function f s.t.:
(1) $f(f(n)) \in O(f(n))$
(2) $f(n) \in \Omega(\cup_i n^i)$
Thanks!
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
The answer is no. By (1), we know that $f(f(n))\leq k f(n)$ for some constant $k$ and sufficiently large $n$. By (2), we get in particular that $c n^2\leq f(n)$ for some constant $c$ and sufficiently large $n$. This implies that $f(n)$ eventually gets large, and so applying it again we get $c (f(n))^2\leq f(f(n))$ for sufficiently large $n$, which implies $c f(n)^2\leq k f(n)$ for sufficiently large $n$, and so $c f(n)\leq k$, which implies $f$ is bounded, contrary to (2).
answered Mar 8, 2011 at 21:15
-
2$\begingroup$ Sorry. This answer is too elegant, too simple, and too correct; try again. If you don't lower the bar for the rest of us on MathOverflow Joel, how do you expect us to keep up? Gerhard "Wish I Thought Of It" Paseman, 2011.03.08 $\endgroup$ Commented Mar 8, 2011 at 22:31
-
2$\begingroup$ Then again, you didn't generalize it to weakening 2) to \Omega(n*g(n)), where g(n) is some slowly increasing non-bounded function, so I guess we can let this answer pass. Gerhard "But On The Other Hand" Paseman, 2011.03.08 $\endgroup$ Commented Mar 8, 2011 at 22:37
-
1$\begingroup$ Gerhard, you flatter me! $\endgroup$ Commented Mar 8, 2011 at 23:21