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
1 Answers
3
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$.
-
0something 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)) – 2011-12-11