Big-O math Question

Question

I'm having trouble with this question:

Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$.

I have tried many ways to approach this question but none work. If anyone can help, I'd appreciate it.

Answer 1

Since $f(x) = O(g(x))$, we have $|f(x)| \leq c \cdot |g(x)|$ for all $x \geq n_{0}$. Similarly, $|g(x)| \leq k \cdot |h(x)|$ for all $x \geq m_{0}$. So take $|f(x)| \leq ck \cdot |h(x)|$ for all $x \geq max\{n_{0}, m_{0}\}$.

Answer 2

It's as simple as considering the $\leq$ transitivity.

Remember that:

If $a \leq b \wedge b \leq c \Rightarrow$ by transitivity, $a \leq c$.

By definition of $O(n)$, if $f(x) \in O(g(x))$: $\exists c$ such that $f(x) \leq c g(x)$.

Thus:

$f(x) \in O(g(x)) \iff f(x) \leq c_{1} g(x)$

$g(x) \in O(h(x)) \iff g(x) \leq c_{2} h(x)$

Then $c_{1} g(x) \leq c_{1}c_{2} h(x)$

Then $f(x) \leq c_{1} g(x) \leq c_{1}c_{2} h(x)$, which by transitivity:

$f(x) \leq c_{1}c_{2} h(x)$ where if you let $ c_{1}c_{2} = c_{3} $, then:

$f(x) \leq c_{3} h(x)$

Then $f(x) \in O(h(x))$ because $\exists c$ such that $f(x) \leq c h(x)$.