1
$\begingroup$

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))$

$\endgroup$
2
  • $\begingroup$ Lucky for you, $O$ does not imply a (single) constant. Check the definition! $\endgroup$ – Raphael Jun 12 '20 at 7:24
  • $\begingroup$ 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 $\endgroup$ – Abhishek Ghosh Jun 13 '20 at 8:42
2
$\begingroup$

I guess the proof is fine except for the fact that you have used same costant in two different eqns. Even if you use(and you must use, because the constant you choose is arbitrary) two different conts say c1 and c2, the solution will imply the same.

$\endgroup$

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.