Max of functions are in big O of the sum of their individual big Os

Question

$\max(f(n), g(n)) = O(f(n) + g(n))$

How do I prove this? Also I'd appreciate the markup being corrected, thanks.

I've never seen the notation O(f(n),g(n)), what does it mean for you? — Yuval Filmus, Nov 14 '10 at 07:43
@Yuval Filmus: Thanks, that was an error. I've corrected it. — Matt Joiner, Nov 14 '10 at 07:46

score 3 · Answer 1 · answered Nov 14 '10 at 07:43

3

You can use $\max(f(n),g(n)) \leq f(n) + g(n)$, given that both functions are non-negative.

answered Nov 14 '10 at 07:43

Yuval Filmus

Does this still hold now that I've changed the operator used? – Matt Joiner Nov 14 '10 at 13:53
@Matt: Now it's immediate. – Yuval Filmus Nov 14 '10 at 18:09

1 Answers1