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

Improve this question
$\endgroup$
12
  • 1
    $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 7:29

1 Answer 1

Reset to default
2
$\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 $$

Improve this answer
$\endgroup$
2
  • 2
    $\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, 2017 at 11:07
  • $\begingroup$ @tipanverella is right in this case. $\endgroup$
    – user3563894
    Sep 18, 2018 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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