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.

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $

where

$(f+g)(n) = f(n) + g(n) $

and

$(\max{f,g})(n) = \max(f(n), g(n))$

I know that $\Theta$ is the combination of the upper and lower bounds, but I can't seem to prove this. It's hard for me to see how $\Theta$ of the max of two functions can be equivalent to $\Theta$ of the two functions added together. Any guidance would be appreciated. Let me know if I can provide more info.

This question is similar, but didn't quite help.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

If $f,g \geq 0$, then $\frac{1}{2}(f+g) \leq \max(f,g) \leq (f+g)$. Rearranging gives $ \max(f,g) \leq (f+g) \leq 2 \max(f,g)$.

It follows that $\Theta(f+g) = \Theta(\max(f,g))$.

Addendum: When we write $a \in \Theta(b)$, it means that there exists $\underline{k}, \overline{k} >0$, and $N$ such that if $n\geq N$, then $\underline{k} b(n) \leq a(n) \leq \overline{k} b(n)$. Note that if $a \in \Theta(b)$, then $\frac{1}{\overline{k}} a(n) \leq b(n) \leq \frac{1}{\underline{k}} a(n)$, and so $b \in \Theta(a)$, hence it is an equivalence relation.

The above shows that if we choose $\underline{k} = \frac{1}{2}$, $\overline{k} = 1, N=1$, then $\underline{k}(f(n)+g(n)) \leq \max(f(n),g(n)) \leq \overline{k}(f(n)+g(n))$, and hence $n \mapsto \max(f(n),g(n)) \in \Theta(n \mapsto f(n)+g(n))$, or, more colloquially, $\max(f,g) \in \Theta(f+g)$, and by the above remark, we also have $f+g \in \Theta(\max(f,g))$.

share|improve this answer
    
Maybe my confusion is dealing with the = sign. Are we saying that the two sets are equivalent? This is where I seem to be having trouble. I understand what you are saying about max<f+g<2max, but I don't see how this proves that the two sets are equal. –  MrZander Jan 31 '13 at 18:24
    
Well, I am sure that you can formalize it, but usually the notation is used very loosely. When one writes $f \in \Theta(g)$, it means for $n$ sufficiently large, there are strictly positive constants $\underline{k}, \overline{k}$ such that $\underline{k} g(n) \leq f(n) \leq \overline{k} g(n)$. When you write $\Theta(f) = \Theta(g)$, the interpretation is that $h \in \Theta(f) $ iff $h \in \Theta(g)$. So I suppose you could define $\Theta(g)$ as the set of $f$s satisfying the above inequalities and all would be fine... –  copper.hat Jan 31 '13 at 18:31
    
Okay, I think I see where you are coming from. I am going to try and formally work this out. –  MrZander Jan 31 '13 at 23:21
    
@MrZander: Note that the inequalities above give explicit constants that show the equality of the $\Theta$ expressions. –  copper.hat Feb 5 '13 at 1:58
    
Why are we able to make the logical step between $\max(f(n),g(n)) \leq (f+g)(n) \leq 2\max(f(n),g(n))$ and $\Theta(f+g)=\Theta(\max(f,g))$? This is what I can't wrap my mind around. –  MrZander Feb 5 '13 at 2:29

Certainly, $\max(f,g) \leq f+g$ so $\max(f,g) = O(f+g)$, and it only remains to establish the lower bound.

If $f = \Theta(g)$, the statement is trivial, so assume $f = O(g)$ and then $2 \max(f,g) = 2g \geq f+g$, which implies $\max(f,g) = \Omega(f+g)$, as desired.

share|improve this answer
    
Could you write this more formally? I don't see how this shows equivalence between the two sets. –  MrZander Jan 31 '13 at 23:17

Just hope this clarifies a bit more:

You want to show that $h(x)=\max(f(x),g(x))=\Theta(f(x)+g(x))$. Observe two cases:

Case1:

$h(x)=f(x)$, hence $f(x) \geq g(x)$. Then $2 h(x) = 2 f(x) \geq f(x) + g(x)$,

$\Leftrightarrow h(x) \geq \frac{f(x)+g(x)}{2}$

$\Leftrightarrow h(x) = \Omega(f(x)+g(x))$ This gives the lower bound.

Next, $h(x)=f(x) \leq f(x)+g(x)=O(f(x)+g(x))$

Hence, $h(x)=\Theta(f(x)+g(x))$

Case 2:

$h(x)=g(x)$. Similar to Case 1.

share|improve this answer
    
I want to show $\Theta(\max(f(x),g(x)))=\Theta(f(x)+g(x))$ –  MrZander Feb 5 '13 at 1:38

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.