6
$\begingroup$

$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)$$

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

The proof is by counterexample. Consider the following functions:

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

$\endgroup$
0
$\begingroup$

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$).

$\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.