prove or disprove
$$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$
I have no idea about where to begin.
what are the theories which should be used here?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Did you try experimenting with some examples for f, g, h? $\endgroup$– Badr BCommented Jan 5, 2020 at 13:02
-
$\begingroup$ No. Actually I couldn't find any references to learn theories or find examples for them $\endgroup$– Kavindu RavishkaCommented Jan 5, 2020 at 13:09
-
$\begingroup$ Start by looking at the definitions. $\endgroup$– JuhoCommented Jan 5, 2020 at 16:11
-
$\begingroup$ $O(g(n))\leq c_1 \cdot g(n)$ for $n >k_1$ and $O(h(n))\leq c_2 \cdot h(n)$ for $n>k_2$. Clearly $c_1\cdot g(n)+c_2\cdot h(n)\leq \max \{c_1,c_2\}\cdot ( g(n)+h(n)) = \max \{c_1,c_2\}\cdot (f(n)).$ You can also choose $k_3 = \max\{k_1,k_2\}$ $\endgroup$– ramseysdream111Commented Jan 5, 2020 at 20:09
Add a comment
|