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)?
Prove the following: if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$ then $f(n)$ is $O(h(n))$
2
$\begingroup$
asymptotics
computational-complexity
-
0"obviously $f(n) \leq Nh(n)$": That's not quite right. – 2011-12-11