patternModerate
Why do Θ-bounds not survive taking differences?
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)$$
$$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.
$$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.