8

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

Michael Hardy
  • 1
Mihai Neacsu
  • 305
  • 4
    The expected answer is probably that the difference is always $O(f(n))$. – hmakholm left over Monica Feb 01 '12 at 17:43
  • 2
    +1 since this notation really opens the door to confusion – Dirk Feb 01 '12 at 20:36
  • 2
    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 01 '12 at 21:16

1 Answers1

15

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

Brian M. Scott
  • 616,228