Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.

share|cite|improve this question
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 1:49
@Jonas Yes.they are non negative. – Bunny Rabbit Dec 22 '10 at 1:53
up vote 0 down vote accepted

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

share|cite|improve this answer
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 2:13
@Bunny: How is that relevant to the hint above? – Aryabhata Dec 22 '10 at 2: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 2:19
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 2:30
@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 2:33

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.