Does $f(n) = O(g(n))$ imply $f(h(n)) = O(g(h(n)))$?
Let's assume for simplicity that $f(n),g(n)$ both take positive integer values. Then $f(n) = O(g(n))$ iff there exists $C&gt;0$ such that $f(n) \leq Cg(n)$ for all $n$. This implies that for any $h\colon \mathbb{N} \to \mathbb{N}$, $f(h(n)) \leq Cg(h(n))$ holds for all $n$, and so $f(h(n)) = O(g(h(n)))$.
In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C&gt;0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim_{n\to\infty} h(n) = \infty$. In particular, there exists $M&gt;0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.