Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
$\displaystyle f(n)=O(g(n))$ means there exist $\displaystyle n_1$ and $\displaystyle M_1$ such that:
$\displaystyle |f(x)| \le M_1|g(n)|\ \forall n>n_1$
and $\displaystyle g(n)=O(g(n))$ means there exist $\displaystyle n_2$ and $\displaystyle M_2$ such that:
$\displaystyle |g(x)|\le M_2|h(n)|\ \forall n>n_2$
Hence:
$\displaystyle |f(x)|\le M_1 M_2 |h(n)|\ \forall n> \max(n_1,n_2)$
Therefore $\displaystyle f(n)=O(h(n))$
RonL