Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$) and $f_2(n)$ = O($g_2(n)$)

then

$f_1$o $f_2$ = O($g_1$ o $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 O definition inequality holds.

Notes: http://www.cs.cmu.edu/~jamiemmt/teaching/su-122/lectures/07-bigo.pdf

UPDATE: We can assume the functions are increasing monotonically.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
I thought big-O was for some $x_0 \in \Bbb{R}$, $\forall x \geq x_0, \dots$ –  Enjoys Math Apr 19 at 22:18
    
For x, where x > x0 –  Rire1979 Apr 19 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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