my assignment is to (dis)prove the following
$ f(n)+o(f(n))=\Theta(f(n)) $
for example:
$ \forall n \geq n', n + \log(n) = c \cdot n $
so far I have:
$ \forall n \geq n', f(n) = o(g(n)) \leftrightarrow f(n) < c \cdot g(n) $ (definition of little-o)
$ \forall n \geq n', f(n) = \Theta(g(n)) \leftrightarrow f(n) = c \cdot g(n) $ (definition of big-$ \Theta $)
Given $ g(n)=o(f(n)) $:
$ f(n)+o(f(n))=f(n)+g(n) $
$ f(n)=c \cdot f(n) $
$ g(n)<c \cdot f(n) $
I feel like I'm going in circles… any suggestions?
Best Answer
Those are not correct statements of the notation. Try something like
$f(n) \in o(g(n))$ when $|f(n)| \lt c|g(n)|$ for all $c\gt 0$ and for all $n \gt n_0$ for some $n_0$
$f(n) \in \Theta(g(n))$ when $k_1|g(n)| \lt |f(n)| \lt k_2|g(n)|$ for some $k_1,k_2 \gt 0$ and for all $n \gt n_0$ for some $n_0$
Instead, you can show that $\frac12 \left|f(n)\right| \le \left|f(n)+o(f(n))\right| \le \frac32 \left|f(n)\right|$ for all sufficiently large $n$, i.e. when $\left|o(f(n))\right| \lt \frac12 \left|f(n)\right|$, and so $f(n)+o(f(n)) \in \Theta (f(n))$.