In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$

Question

I have to prove that: $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$ (functions are non-negative)

Clarification: $\mathcal{O}(f(n)+g(n))=\mathcal{f(n)}$ it means $\mathcal{O}(f(n)+g(n))\subseteq\mathcal{O}(f(n))\land\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n)+g(n))$

I try to explain my argument, i want to get on one side $f(n)+g(n)\in\mathcal{O}(f(n))$ and on the other: $f(n)\in\mathcal{O}(f(n)+g(n))$ in order to conclude that $\mathcal{O}(f(n)+g(n))=\mathcal{f(n)}$ is true.

I start with the hypothesis:

$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\iff g(n)\in\mathcal{O}(f(n))$ $\iff(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)\leq c_1f(n),\forall n\geq n_0) \implies$ $\{$adding $f(n)$ to both members of the inequality$\}$ $(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1f(n)+f(n),\forall n\geq n_0)\implies\quad(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq (c_1+1)f(n),\forall n\geq n_0)\implies \{\textrm{taking}\quad c_1^{'}=(c_1+1)\}\quad (\exists c_1^{'}\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1^{'}f(n),\forall n\geq n_0)\iff \{by\quad definition\quad of \quad Oh-big \quad order\}\quad f(n)+g(n)\in\mathcal{O}(f(n))$

Now to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ start from the trivial proposition: $\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))$:

$\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))\iff f(n)\in\mathcal{O}(f(n))\iff(\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n),\forall n\geq n_0)\implies$ $\{$adding $g(n)$ to right member of inequality$\}\quad (\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n)+g(n),\forall n\geq n_0)$

At this point I'm stuck I don't know how to continue in order to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ to finish then the proof...

Thanks to everyone who read this :)

Answer 1

About your particular question

Notice: $$f(n)\leq c_2f(n)+g(n) \leq c_2f(n) + c_2g(n) = c_2(f(n) + g(n)) \Rightarrow f(n) \in O(f(n) + g(n))$$ and you get the desirable result.

About problem in general

Let $A, B$ be sets. If you want to prove that $A = B$. There are at least two ways to do it.

1. Prove $A \subseteq B$ and $B \subseteq A$. You chose this one in your question.
2. Assume that $A \neq B$ and then prove that it is impossible.

Alternative proof by second method

Assume $O(f(n)) \neq O(f(n) + g(n))$.

It implies that there is some function $h(n)$ that belongs either to $O(f(n) + g(n))$ or to $O(f(n))$.

Without loss of generality let assume $h(n) \not \in O(f(n))$ and $h(n) \in O(f(n) + g(n))$, other case can be proven in the same way.

$O(g(n)) \subseteq O(f(n)) \Rightarrow \exists c_1 > 0 \ g(n) \leq c_1 \cdot f(n)$

Then since $h(n) \in O(f(n) + g(n)) \Rightarrow \exists c_2 > 0 \ h \leq c_2(f(n) + g(n)) \leq c_2(f(n) + c_1f(n)) = c_2(c_1 + 1)f(n)$.

Let $$c_3 := c_2(c_1 + 1) \Rightarrow h(n) \leq c_3f(n) \Rightarrow h(n) \in O(f(n)) \Rightarrow $$ our initial assumption is wrong $\Rightarrow$ then we can conclude that $h(n) \in O(f(n) + g(n)) \Rightarrow h \in O(f(n))$.

I encourage you to finish this proof by investigating the second case, i.e $$h(n) \in O(f(n)) \land h(n) \not \in O(f(n) + g(n))$$

Answer 2

Suppose $h\in\mathcal O(f(n)+g(n))$, meaning that there exists $C_0>0$, $N_0\in\mathbb N$ such that for all $n\geq N_0$, $|h(n)|\leq C_0(f(n)+g(n))$. Define $h_1(n)=C_0f(n)$ and $h_2(n)=|h(n)|-C_0f(n)$. It is clear that $h_1\in\mathcal O(f(n))$. In addition, because $|h_2(n)|\leq C_0g(n)$, we have that $h_2\in\mathcal O(g(n))$.

By the assumption that $\mathcal O(g(n))\subseteq\mathcal O(f(n))$, we know that $h_2\in\mathcal O(f(n))$ as well. Hence, there exists constant $C_1>0$, $N_1\in\mathbb N$ such that for all $n\geq N_1$, $|h_1(n)|\leq C_1f(n)$. Also, there exists constant $C_2>0, N_2\in\mathbb N$ such that for all $n\geq N_2$, $|h_2(n)|\leq C_2f(n)$. Now define $C := C_1+C_2$ and $N := \max\{N_1,N_2\}$. Then for any $n\geq N$, $|h(n)|\leq |h_1(n)|+|h_2(n)| \leq (C_1+C_2)f(n) \leq Cf(n)$. Therefore, $h\in\mathcal O(f(n))$.