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.

  • $\begingroup$ I think this question is more appropriate for math.se, the sister site on mathematics. $\endgroup$ – Yuval Filmus Aug 3 '17 at 17:01
  • $\begingroup$ The task has nothing to do with data structures. What have you tried and where did you get stuck? Hint: apply the definitions. $\endgroup$ – Raphael Aug 3 '17 at 19:53
  • $\begingroup$ what means $\Theta(f(n)+g(n))$? $\endgroup$ – miracle173 Aug 3 '17 at 20:37
  • $\begingroup$ @miracle173 Check the definition. $\endgroup$ – David Richerby Aug 4 '17 at 9:36
  • $\begingroup$ @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. $\endgroup$ – 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. $$

| cite | improve this answer | |
  • $\begingroup$ still don't get it. could you please explain it a bit more please $\endgroup$ – Ilia Naleva Aug 3 '17 at 16:56
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Aug 3 '17 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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