# 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.

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

• I thought big-O was for some $x_0 \in \Bbb{R}$, $\forall x \geq x_0, \dots$ – BananaCats Category Theory App Apr 19 '14 at 22:18
• For x, where x > x0 – Rire1979 Apr 19 '14 at 22:26
• @EnjoysMath Hm, true, I was sloppy there. The conclusions still hold, though, once just needs to replace "forall $x$" by "forall $x > x_0$". – fgp Apr 19 '14 at 22:29

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.