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!



Growth of Functions
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). 


