how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

Question

though the big O case is simple since $\max(f(n),g(n)) \leq f(n)+g(n)$

edit : where $f(n)$ and $g(n)$ are asymptotically nonnegative functions.

It is false by the common mathematical definition: $f(n) = n, g(n) = -n$. What definition of BigOh are you using? (I know you have tagged it algorithms, so I believe I can guess, but just making sure...) — Aryabhata, Dec 22 '10 at 01:49

Aryabhata · Accepted Answer · 2014-04-17T16:05:46.987

2

Hint...: $2 + 100 \le 100 + 100$

For the sake of completeness:

Use the fact that: $\max(f,g) \le f + g \le 2\max(f,g)$ when $f,g$ are non-negative

edited Apr 17 '14 at 16:05

answered Dec 22 '10 at 01:58

Aryabhata

i don't know whatever the constant n0 we choose , the $f(n0)+g(n0) < = max(f(n0),g(n0))$ is not going to hold, since they are non negative. – Bunny Rabbit Dec 22 '10 at 02:13
@Bunny: How is that relevant to the hint above? – Aryabhata Dec 22 '10 at 02:18
only if the above condition holds for some constant n0 then we can prove the $\omega$ case i.e the lower bound. – Bunny Rabbit Dec 22 '10 at 02:19
@Bunny: Huh? I really suggest you put some thought into it. What I wrote is just a hint. Even a little more, and I have given you the solution. – Aryabhata Dec 22 '10 at 02:21
1

Okay got it , i had actually not noticed that there can be two different constant for lower bound and the upper bound respectively , Thanks,that you didn't give away the whole solution , the hint made this lazy fella work a little , thanks a lot. – Bunny Rabbit Dec 22 '10 at 02:30
1

@Bunny: Glad it helped. If the constant is same for lower and upper bound, then they both have to be equal! So you can rule that out :-) – Aryabhata Dec 22 '10 at 02:33

1 Answers1