6

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.

Community
  • 1
MrZander
  • 173

3 Answers3

7

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.

gt6989b
  • 54,422
6

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

copper.hat
  • 172,524
  • 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 05 '13 at 01: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 05 '13 at 02:29
  • @MrZander: I have added an elaboration to the answer; hopefully it addresses your concerns? – copper.hat Feb 05 '13 at 02:52
  • 2
    Jesus god. Took me like 30 minutes to understand what was going on here – Shammy Oct 03 '15 at 18:26
  • 1
    @Shammy: Thanks :-). Your comment produced a guffaw on this end... – copper.hat Oct 03 '15 at 18:30
  • I'm similarly solving this problem. Is it correct to let say $f(n) + g(n) \le c * $ max$ {(f(n), g(n)}$ which $\implies f(n) + g(n) = O($ max ${f(n), g(n)}$ – Shammy Oct 03 '15 at 18:33
  • @Shammy: As long as $c \ge 2$. – copper.hat Oct 03 '15 at 18:34
  • So then when $c = 1$ and only when $c = 1$ I can say that $f(n) + g(n) = \Theta($ max $ {f(n), g(n)}$ ? – Shammy Oct 03 '15 at 18:38
  • Augh now I'm confusing my self. – Shammy Oct 03 '15 at 18:39
  • 1
    @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 03 '15 at 18:42
  • Oh oh, ok I get it. Thanks – Shammy Oct 03 '15 at 18:46
1

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.

Alex
  • 19,262