0
$\begingroup$

I'm doing a practice question (not graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly.

Suppose $f(n) = O(g(N))$ and $g(n) = O(h(n))$ (all functions are positive).

Prove that $f(n) = O(h(n))$.

I am having lots of trouble with this, and it would be greatly helpful if someone showed me how to do this.

$\endgroup$
3
$\begingroup$

Consider using the definition of Big-O. If $f(n) \in O(g(n))$, then there exists a $c, n_0 > 0$ such that $f(n) \leq cg(n)$ for all $n \geq n_0$. Similarly, we can write a similar inequality for $g(n)$. We have that if $g(n) \in O(h(n))$, then there exists a $d, n_1 > 0$ such that $g(n) \leq dh(n)$ for all $n \geq n_1$.

To show what you are trying to show, consider putting both pieces together. Not only do we know that $f(n) \leq cg(n)$, but we also know that $g(n) \leq dh(n)$. Putting these two together gives $f(n) \leq c'h(n)$ where $c' = c \cdot d$, for the appropriate conditions. Can you verify what those are? In particular, for what values of $n$ does this hold?

From there, the desired result follows by definition of Big-O.

$\endgroup$
  • $\begingroup$ is it that n> n1 and n > n0 ? $\endgroup$ – Jonathan Sep 26 '16 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.