# Why do Θ-bounds not survive taking differences?

$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that:

$$f_1 = \Theta(f_2)$$ $$g_1 = \Theta(g_2)$$

I was able to prove that:

$$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$

But I can't understand why the following statment is not necessarily true:

$$f_1 - g_1 = \Theta(f_2 - g_2)$$

• I would recommend trying to write out the proof and see what (if anything) goes wrong. – Yuval Filmus Sep 20 '14 at 0:40

$$f_1(x) = 2x$$ $$f_2(x) = x+1$$ $$g_1(x) = x$$ $$g_2(x) = x$$
First, we can see that $f_1 = \Theta(f_2)$ and $g_1 = \Theta(g_2)$. Finding constants to prove the four big-Oh relationships involved is straightforward (in particular for $g_1$ and $g_2$).
Next, we can observe that $f_1 - g_1 = x \neq \Theta(1) = \Theta(f_2 - g_2)$.
Notice that the choice of $2$ and $1$ for the above functions is unimportant, so long as you choose them so that the difference between $f_1$ and $g_1$ is more than constant and the difference between $f_2$ and $g_2$ is constant.
If $f_2 = o(g_2)$ then it is indeed the case that $f_1 = \Theta(f_2)$ and $g_1 = \Theta(g_2)$ imply that $|f_1 - g_1| = \Theta(|f_2 - g_2|)$ = \Theta(f_2). Same works if $g_2 = o(f_2)$. Otherwise there no guarantee possible – you can easily come up with examples in which $|f_1-g_1| = o(|f_2-g_2|)$ (for example $f_1=g_1=f_2=n$ $g_2=2n$) or $|f_1-g_1| = \omega(|f_2-g_2|)$ (for example $f_2=g_2=f_1=n$, $g_1=2n$).