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

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))$$ The functions are non-negative.

Clarification: $$\mathcal{O}(f(n)+g(n))=\mathcal{O}(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{O}(f(n))$ 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 :)

• You seem to be using $O(f(n)+g(n))=f(n)$ and $f(n)=O(f(n)+g(n))$ to mean different things. They don't mean different things, so what do you mean? Jun 22, 2017 at 12:30
• sorry, i had copied and pasted at final f(n)+g(n) <= c2*f(n)+g(n) but is f(n) <= c2*f(n)+g(n), now corrected Jun 22, 2017 at 13:04
• Well, your way seems to be long and difficult. Why didn't you use the fact that $\exists c\in \mathbb{R^+}\ \forall g(n) \forall f(n) : g(n)\leq c\cdot f(n)$? Jun 22, 2017 at 13:05
• @JhonsonB. In your second paragraph, you say that you need to prove that $f\in O(f+g)$ to prove that $O(f+g) = f$. That's a tautology but the fact that you've written it suggests you think it isn't. Jun 22, 2017 at 13:32
• I'm voting to close as unclear, since the asker hasn't clarified what the introduction to their question is supposed to mean. Jun 23, 2017 at 7:29

## 1 Answer

I think you are pretty much done.

$$g(n) \ge 0 \implies f(n) \le f(n) + g(n), \quad \forall n \in \mathbb{N}$$

So pick $c = 1 \in \mathbb{R}^+$ and $n_0 = 1 \in \mathbb{N}$, then $$f(n) \le c\cdot(f(n) + g(n)), \quad \forall n\ge n_0$$

• I think you should show that $f(n) + g(n) \leq cf(n)$ for fixed $c$ and $n > n_0$. Nov 21, 2017 at 11:07
• @tipanverella is right in this case. Sep 18, 2018 at 2:29