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)?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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$.