0
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Richerby Jun 22 '17 at 12:30
  • $\begingroup$ 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 $\endgroup$ – Jhonson B. Jun 22 '17 at 13:04
  • $\begingroup$ 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)$? $\endgroup$ – rus9384 Jun 22 '17 at 13:05
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jun 22 '17 at 13:32
  • 1
    $\begingroup$ I'm voting to close as unclear, since the asker hasn't clarified what the introduction to their question is supposed to mean. $\endgroup$ – David Richerby Jun 23 '17 at 7:29
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think you should show that $f(n) + g(n) \leq cf(n)$ for fixed $c$ and $n > n_0$. $\endgroup$ – clemens Nov 21 '17 at 11:07
  • $\begingroup$ @tipanverella is right in this case. $\endgroup$ – user3563894 Sep 18 '18 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.