How to prove that if $f(n)=O(g(n))$ then $f(h(n))=O(g(h(n)))$?

Question

$f,g,h:\mathbb N\to \mathbb N$ are increasing functions. Prove that if $f(n)=O(g(n))$ then $f(h(n))=O(g(h(n)))$.

This makes sense intuitively: all of the functions are increasing. Then composition of two increasing functions is also increasing. But how can I prove this rigorously using big-O notation?

Answer 1

What you know:

There exists some constant $M$ and some $n_0$ such that $f(n)<M\cdot g(n)$ for all $n>n_0$.

Also, you know that $f,g,h$ are increasing.

---

What you need to prove:

There exists some constant $M'$ and some $n_0'$ such that $f(h(n))<M\cdot g(h(n))$ for all $n>n_0$.

---

Idea of proof:

Since $h(n)$ is increasing, $h(n)$ will eventually hit only big numbers, meaning $f(h(n))$ will still be under $Mg(h(n))$.

---

ACTUAL PROOF:

The main thing to notice is that it is fairly easy to prove that $$\forall n\in\mathbb N: h(n)>n$$

(this can be proven by induction).

Once you have that, just taking $M'=M$ and $n_0'=n_0$ will be enough, since, if $n>n_0$, then $h(n)>n>n_0$, and since $h(n)>n_0$, by assumption, we have $$f(h(n))<M\cdot g(h(n))$$

which (since $M'=M$) is exactly what we wanted to show.