HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why do Θ-bounds not survive taking differences?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whysurvivedifferencesboundsnottaking

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#30141, answer score: 12

Revisions (0)

No revisions yet.