Sign up ×
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) $


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


$(\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|cite|improve this question

3 Answers 3

up vote 5 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|cite|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
@Shammy: Thanks :-). Your comment produced a guffaw on this end... – copper.hat Oct 3 at 18:30
@Shammy: I'm not exactly sure what you are asking. Remember that the whole 'O' thing represents a collection of functions, so when we write $h \in \Theta(f+g)$ is means there is some $a,b>0$ and $N>0$ such that if $n \ge N$, then $a(f(n)+g(n)) \le h(n) \le b (f(n)+g(n))$. The above just shows that $\Theta(f+g) = \Theta(\max(f,g))$. – copper.hat Oct 3 at 18:42

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|cite|improve this answer

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:


$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|cite|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


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.