# proof that a function plus a lower growth function is theta the first function.

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?

-
$n + \log(n) = c*n$ is not true for any $c$ if $n$ varies – Henry Sep 14 '12 at 23:50

Suppose that $g(n)$ is $o(f(n))$, and let $h(n)=f(n)+g(n)$; you want to prove that $h(n)$ is $\Theta(f(n))$.

To show that $f(n)$ is $\Theta(h(n))$, you must show that there are positive constants $C_1,C_2$, and $n_0$ such that $C_1|f(n)|\le|h(n)|\le C_2|f(n)|$ for all $n\ge n_0$.

Note: My $n_0$ corresponds to your $n'$. Note that in your post you have the inequalities involving $n$ and $n'$ backwards: you want something to be true for all $n$ from some point on, not just for all $n$ up to some point. Your definitions of $o$ and $\Theta$ are seriously off in other respects as well; you should check them against your text or this article.

Unpacking $h$, we want $C_1|f(n)|\le|f(x)+g(x)|\le C_2|f(n)|$ for all $n\ge n_0$. Since $g(n)$ is $o(f(n))$, we know that for each $\epsilon>0$ there is an $n_\epsilon$ such that $|g(n)|<\epsilon|f(n)|$ whenever $n\ge n_\epsilon$. Take $\epsilon=\frac12$, and let $n_0=n_{1/2}$. Then whenever $n\ge n_0$ we have $|g(n)|\le\frac12|f(n)|$, so

$$\frac12|f(n)|=|f(n)|-|g(n)|\le|f(x)+g(x)|\le|f(n)|+|g(n)|\le\frac32|f(n)|\;,$$

and we see that $C_1=\frac12$ and $C_2=\frac32$ do the trick with this value of $n_0$.

-
fixed the inequalities, thanks. – Ocasta Eshu Sep 14 '12 at 23:46

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

-
just using the notation from books.google.com/books/about/…, but I'll check out the wiki also. – Ocasta Eshu Sep 14 '12 at 23:42
Sometimes definitions are slightly careless about absolute values. Your authors are not careless. They make the explicit assumption that all the functions they mention are asymptotically non-negative. – André Nicolas Sep 14 '12 at 23:58
If it's good enough for Hardy and de Bruijn, it's good enough for me. To me, using "$\in$" instead of "=" when doing O work is needless formalism. – marty cohen Sep 15 '12 at 3:07