Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?
First, let us note that for monotone $f$, the statement holds for some $c &gt; 1$ iff it holds for all $c &gt; 1$. Indeed, let $1 &lt; c_1 &lt; c_2$. If the statement holds for $c_2$ then $f(c_1n) \leq f(c_2n) = O(f(n))$ due to monotonicity. In the other direction, let $M$ be an integer so that $c_2 \geq c_1^M$. Then induction shows that $f(c_1^Mn) = O(f(n))$, and so $f(c_2n) = O(f(n))$ due to monotonicity.

If $f$ is a polynomial then $f(n) = \Theta(n^A)$ and so $f(cn) = \Theta((cn)^A) = \Theta(n^A) = \Theta(f(n))$. A similar argument works when $\Omega(n^{A-o(1)}) \leq f(n) \leq O(n^{A+o(1)})$.

In the other direction, suppose that $f(n) = n^{g(n)}$, and suppose that $g(n)$ is nondecreasing. Then $f(cn) \geq c^{g(n)} f(n)$, and so $f(cn) = O(f(n))$ iff $g(n)$ is bounded. So in some sense, if $f(cn) = O(f(n))$ then $f$ must have polynomial growth.