# Prove the following: if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$ then $f(n)$ is $O(h(n))$

I understand that $f(n) \leq Ng(n)$ and $g(n) \leq Nh(n)$ so obviously $f(n) \leq Nh(n)$, but how would one go about proving this using proper semantics (using big $O$ notation)?

-
"obviously $f(n) \leq Nh(n)$": That's not quite right. – TonyK Dec 11 '11 at 10:20

## 1 Answer

Well, when $f(n)$ is $O(g(n))$, you should have an associated constant $K_f$ and some $N_f$. Then, when $g(n)$ is $O(h(n))$, you have an associated constant $K_h$ and some $N_h$.

Take the larger of the two $N$ (or their sum, or their product, etc) and take $K_f K_h$ to be the new constant. This will give you the asymptotic $n$ and $k$ so that $f(n) < kh(n)$ for all sufficiently large $n$.

-
something like this then? f(n) = O(g(n)) f(n) <= N(g(n) g(n) = O(h(n)) g(n) <= N1(h(n)) so f(n) <= N(g(n)) and g(n) <= N1(h(n)) f(n) <= N(g(n)) <= N1*N(h(n)) – Doug Masters Dec 11 '11 at 3:43