5
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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))$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MrZander Jan 31 '13 at 18:24
  • $\begingroup$ 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... $\endgroup$ – copper.hat Jan 31 '13 at 18:31
  • 2
    $\begingroup$ Jesus god. Took me like 30 minutes to understand what was going on here $\endgroup$ – Shammy Oct 3 '15 at 18:26
  • 1
    $\begingroup$ @Shammy: Thanks :-). Your comment produced a guffaw on this end... $\endgroup$ – copper.hat Oct 3 '15 at 18:30
  • 1
    $\begingroup$ @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))$. $\endgroup$ – copper.hat Oct 3 '15 at 18:42
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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