Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
