Prove of a Landau-equalities I have to prove or disprove the following Landau-equalities:
$$ O(f+g) = O(max(f,g))$$
and $$O(f-g) = O(min(f,g))$$
with $f,g: \mathbb N \to \mathbb R^+$ .
To show equality of two sets, one has to show that the first is a subset of the second and vice versa, thus:
$O(f+g) \subseteq O(max(f,g)) $ and $ O(max(f,g)) \subseteq O(f+g)$
My problem is the step from sets to functions . Can you help me out?
 A: To show that $O(f+g)\subseteq O(\max(f,g))$, say, let $r$ be an element of $O(f+g)$. Then $r$ is a function of $n$ with the property that there exist positive numbers $C$ and $N$ such that $n \ge N$ implies $|r(n)| \le C(f(n)+g(n))$. Now, note that $$a + b = \min(a,b) + \max(a,b) \le \max(a, b) + \max(a, b) = 2\max(a,b)$$ for any numbers $a$ and $b$. Can you go from here?
A: $$h(x)=\mathcal O(f(x)+g(x))\iff \exists \delta>0,\exists C>0:\forall |x|<\delta, \left|h(x)\right|<C|f(x)+g(x)|$$$$<2C\max\{|f(x)|,|g(x)|\}$$
therefore $$h(x)=\mathcal O(\max\{f(x),g(x)\})$$
I let you do the other one, the proof goes in the same way ;-)
A: We set $h=O(f+g)$.
So it suffices  to prove that $h=O(\max\{f,g\})$, i.e. that    $\exists c>0, n_0 \in \mathbb{N}$ such that $\forall n \geq n_0$: $h \leq c \max\{ f,g \}$
We know that $h=O(f+g)$.
By definition that means that $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1:$
$$h \leq c_1(f+g)$$
So, we have
$\forall n \geq n_1:$
$$h \leq c_1(f+g) \Rightarrow h \leq c_1 (\max\{ f,g \}+\max\{ f,g \})=2c_1 \max\{ f,g \}$$
We pick $n_0=n_1$ and $c=2c_1$ and we have that:
$$h=O(\max\{ f,g \}) \Rightarrow O(f+g)=O(\max\{ f,g \}) $$
