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

3 Answers 3

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.

$\endgroup$
0
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))$.

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

$\endgroup$
1
  • $\begingroup$ I want to show $\Theta(\max(f(x),g(x)))=\Theta(f(x)+g(x))$ $\endgroup$
    – MrZander
    Commented Feb 5, 2013 at 1:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .