Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
how can be prove that $\max(f(n),g(n)) = \theta(f(n)+g(n))$

How to prove $max(f(n),g(n)) = Θ(f(n)+g(n))$?

share|improve this question

marked as duplicate by J. M., JavaMan, anon, Zev Chonoles Sep 8 '11 at 20:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Is $\Theta(f(x))$ the same as $O(f(x))$ of "big-O" fame? –  robjohn Sep 8 '11 at 19:08
1  
@robjohn: $f = \Theta(g)$ if both $f = O(g)$ and $g = O(f)$. –  JavaMan Sep 8 '11 at 19:16

1 Answer 1

up vote 3 down vote accepted

Let $h=\max(f,g)$. Then $f+g\le 2h$ and so $f+g=O(h)$. If $f$ and $g$ are positive, then $h \le f+g$ and so $h=O(f+g)$.

share|improve this answer

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