Prove of a Landau-equalities

Question

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?

Answer 1

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

Answer 2

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?

Answer 3

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