Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
The expected answer is probably that the difference is always $O(f(n))$. –  Henning Makholm Feb 1 '12 at 17:43
2  
+1 since this notation really opens the door to confusion –  Dirk Feb 1 '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 1 '12 at 21:16
add comment

1 Answer

up vote 17 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.