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.

Yuval Filmus · Answer 1 · 2010-11-14 07:43:54Z

up vote 3 down vote

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 7:43

Yuval Filmus
25.9k2871

	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 Answer