Big-O and function composition

On the last page of this document, a property of big-O operations is listed which says that if $$f_1(n) = O(g_1(n))\text{, and } f_2(n) = O(g_2(n))$$ Then $$f_1 \circ f_2 = O(g_1 \circ g_2)$$

Why is that?

Trying to get this to a form that resembles the definition I get to:

$$f_1(f_2(n)) = k_1 * g_1(g_2(n))$$

and I'm kind of stuck... I don't see how the big-O definition inequality holds.

UPDATE: We can assume the functions are increasing monotonically.

Solution 1:

This is false unless you make extra assumptions. Assume that $f_2(x) = 2x$, $g_2(x) = x$. Then $f_2(x) = O(g_2(x))$. Now take $f_1(x) = g_1(x) = e^x$. Then you get $f_1(f_2(x)) = e^{2x}$ and $g_1(g_2(x)) = e^x$, and $e^{2x} \neq O(e^x)$ so there's something wrong.

Solution 2:

"$f = O(g)$" means that for some $c$ and some $x_0$, $f(x) \leq c\cdot g(x)$ for all $x \geq x_0$.

So, if $f_1 = O(g_1)$ and $f_2 = O(g_2)$, there are $c_1,c_2$ and an $x_0$ with $$ f_1(x) \leq c_1 g(1) ,\quad f_2(x) \leq c_2g_2(x) \text{ for all $x > x_0$.} $$ So what, then, can we say about $f_1 \circ f_2$?. We have for every $x > x_0$ that $$ y = f_2(x) \leq c_2g_2(x) $$ and therefore $$ (f_1 \circ f_2)(x) = f_1(y) \leq c_1g_1(y) \text{.} $$ If we additionally assume that $g$ increases monotonically, then we can replace $y$ with the larger value $c_2g_2(x)$ in that last inequality to get $$ (f_1 \circ f_2)(x) = f_1(y) \leq c_1g_1(c_2g_2(x)) \text{.} $$ which implies that $$ f_1 \circ f_2 = O(g_1 \circ c_2g_2) \text{.} $$

user2566092's example shows that we cannot, in general, get rid of that factor $c_2$ there. Though if, for example, $g_1(x) = x^n$, then $g_1(c_2g_2(x)) = (c_2g_2(x))^n = c_2^n (g_2(x))^n = O((g_1)^n)$, so for these $g_1$ you indeed have $$ f_1 \circ f_2 = O(g_1 \circ g_2) \text{.} $$

The general property that you need for your proposition to hold is thus that $$ g_1(c\cdot x) = O(g_1(x)) \text{.} $$