Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n))

Tag: big-o , analysis , asymptotic-complexity , proof Author: fengyangfrances Date: 2013-04-16
Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n))

It does make sense, but so far I don't have any idea how to actually prove it.

Any input would be appreciated.

What is the commas meaning in O(f(n), g(n))? I only know O(f(n)).
It was my mistake. It should have been max(O(f(n), O(g(n))).

Best Answer

f(n) <= max(f(n), g(n))
g(n) <= max(f(n), g(n))

max(O(f(n)), O(g(n))) <= O(max(f(n), g(n)), max(f(n), g(n))) = O(max(f(n), g(n)))

Note that the in-equalities used are not strict.

comments:

How can you assume polynomial time without losing generality?
@Ryan: Point taken
Thank. Just to note that the last expression should be max(O(f(n)), O(g(n))) = O(max(f(n), g(n))
Edited to fix the brackets as well as to make it more explicit to derive RHS from LHS