# Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$

Show that $$O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$$

Can I keep the same constant $$c$$ in each of the cases?

Consider two cases: $$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c⋅f(n);c>0$$ $$2)f(n)≤g(n);O(\text{max}\{f(n),g(n)\})⇒O(g(n))\Rightarrow e(n)≤c⋅g(n);c>0$$ Combining the 2 cases yields: $$d(n)+e(n)≤c⋅f(n)+c⋅g(n)$$ $$d(n)+e(n)≤c⋅(f(n)+g(n))$$ Which is definition of $$O(f(n)+g(n))$$

• Lucky for you, $O$ does not imply a (single) constant. Check the definition! – Raphael Jun 12 '20 at 7:24
• Everything is fine except for the same constant part. Assume $c_1$ and $c_2$ and then while combining assume another constant $c$ with $c>c_1$ and $c >c_2$ using this assumption... Get an inequality from the inequations 1 and 2 and then while adding the inequalities as you did, replace $c_1$ and $c_2$ by $c$ and from your assumption you have ur answer – Abhishek Ghosh Jun 13 '20 at 8:42