Prove transitivity of big-O notation

Problem Detail: 

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.

Asked By : STC

Answered By : user340082710

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37721