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