3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.