# What is $Θ(f(n)) - Θ(f(n))$?

$$\Theta(f(n)) - \Theta(f(n)) =\; ?$$

I find this exercise from my algorithm analysis book very confusing because it's subtracting 2 function sets. Any hints/answers are welcome.

Thanks!

-
The expected answer is probably that the difference is always $O(f(n))$. –  Henning Makholm Feb 1 '12 at 17:43
+1 since this notation really opens the door to confusion –  Dirk Feb 1 '12 at 20:36
That question is badly abusing notation. Much like the abuse found in the a statement like $n^2+5n+1=O(n^2)$, rather than $n^2+5n+1 \in O(n^2)$. The same question with minimal abuse of notation might be $\left\{ g-h|g,h\in\Theta(f)\right\} = ?$, given that you understand that $g$, $h$, and $f$ are single variable functions rather than scalars. –  Kevin Cathcart Feb 1 '12 at 21:16

The question can be rephrased as follows:

Suppose that $g(n)$ and $h(n)$ are both $\Theta(f(n))$; what can be said about the asymptotic behavior of $g(n)-h(n)$?

Since $g$ and $h$ have similar behavior, you might at first think that $g-h$ would be $\Theta(1)$, but very simple examples show that this can’t in general be true: take $g(n)=2n$ and $h(n)=f(n)=n$, for instance. On the other hand, $g-h$ certainly can be constant, since it can be the zero function. Thus, you can’t expect to put a lower bound on $g-h$ and say that it’s $\Omega(\text{something})$; the best that you can hope for is an upper bound on the growth of $g-h$.

To avoid cluttering the notation, I’m going to assume that the functions are positive; if not, insert absolute values as needed.

You know that there are positive constants $c_g$ and $C_g$ and a natural number $n_g$ such that $$c_gf(n)\le g(n)\le C_gf(n)$$ whenever $n\ge n_g$. Similarly, there are $c_h,C_h>0$ and $n_h\in\mathbb{N}$ such that $$c_hf(n)\le h(n)\le C_hf(n)$$ whenever $n\ge n_h$. Then $$g(n)-h(n)\le (C_g-c_h)f(n)$$ and $$h(n)-g(n)\le (C_h-c_g)f(n)$$ whenever $n\ge\max\{n_g,n_h\}$. Therefore $$|g(n)-h(n)|\le \dots\quad ?$$ whenever $n\ge\max\{n_g,n_h\}$.

-
Thank you, sir! It seems so natural now! –  Mihai Neacsu Feb 1 '12 at 18:43
Conversely, given $u(n) \in O(f)$, we can find $g, h \in \Theta(f)$ such that $g - h = u$. That is, if we define $\Theta(f) - \Theta(f)$ to be the differenceset $\{ g-h : g, h \in \Theta(f) \}$, then $\Theta(f) - \Theta(f)$ and $O(f)$ are equal as sets. –  Srivatsan Feb 1 '12 at 19:46
"You know that there are positive constants c_g and C_g and a natural number n_h such that" Didn't you mean n_g? –  Daniil Feb 6 '12 at 16:35
@Daniil: I did indeed; thanks. –  Brian M. Scott Feb 6 '12 at 18:05