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.
 A: 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. 
A: "$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{.}
$$
