- #1
evinda
Gold Member
MHB
- 3,741
- 0
Hello! (Smile)
I want to prove or disprove the statement $f(n)+o(f(n))=\Theta(f(n))$.
Do I have to set $g(n)=o(f(n))$ and use the definition, that is that $\forall c>0, \exists n_0(c) \in \mathbb{N}$ such that $\forall n \geq n_0: 0 \leq g(n)<cf(n)$ ? (Thinking)
Is the following right?
We set $g(n)=o(f(n))$.That means that $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0: 0 \leq g(n)< cf(n)$.
So: $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n), \forall n \geq n_0$.
Right? So do we say that $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n) \Rightarrow f(n) \leq f(n)+g(n) \leq (c+1)f(n), \forall n \geq n_0$
So picking $c_1=1, c_2=c+1$ we see that $f(n)+g(n)=\Theta(f(n)) \Leftrightarrow f(n)+o(g(n))=\Theta(f(n))$.
I want to prove or disprove the statement $f(n)+o(f(n))=\Theta(f(n))$.
Do I have to set $g(n)=o(f(n))$ and use the definition, that is that $\forall c>0, \exists n_0(c) \in \mathbb{N}$ such that $\forall n \geq n_0: 0 \leq g(n)<cf(n)$ ? (Thinking)
Is the following right?
We set $g(n)=o(f(n))$.That means that $\forall c>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0: 0 \leq g(n)< cf(n)$.
So: $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n), \forall n \geq n_0$.
Right? So do we say that $f(n) \leq f(n)+g(n) < cf(n)+f(n)=(c+1)f(n) \Rightarrow f(n) \leq f(n)+g(n) \leq (c+1)f(n), \forall n \geq n_0$
So picking $c_1=1, c_2=c+1$ we see that $f(n)+g(n)=\Theta(f(n)) \Leftrightarrow f(n)+o(g(n))=\Theta(f(n))$.
Last edited:
