2
$\begingroup$

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)?

  • 0
    "obviously $f(n) \leq Nh(n)$": That's not quite right.2011-12-11

1 Answers 1

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$.

  • 0
    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))2011-12-11