# Proving that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

Prove that for every two positive functions $f(n),g(n)$: $$\max(f(n),g(n)) = \Theta(f(n)+g(n)).$$

I've just started data structures and I barely understand it, so please be gentle with me.

• I think this question is more appropriate for math.se, the sister site on mathematics. – Yuval Filmus Aug 3 '17 at 17:01
• The task has nothing to do with data structures. What have you tried and where did you get stuck? Hint: apply the definitions. – Raphael Aug 3 '17 at 19:53
• what means $\Theta(f(n)+g(n))$? – miracle173 Aug 3 '17 at 20:37
• @miracle173 Check the definition. – David Richerby Aug 4 '17 at 9:36
• @DavidRicherby Thank you, but I know the definition, but I think it would be useful for the user and the post if it is added to the question. Especially if he reads YuvalFilmus' answer. It also would show some effort to solve the question. – miracle173 Aug 4 '17 at 9:42

This follows from the inequality $$\frac{a+b}{2} \leq \max(a,b) \leq a+b.$$ To prove this, assume that $a \leq b$. You need to show that this implies that $$\frac{a+b}{2} \leq b \leq a+b.$$
• It's an exercise. Supplying a complete answer will ruin the point of the exercise. Try relating the definition of big $\Theta$ to what I wrote. – Yuval Filmus Aug 3 '17 at 17:02