0
$\begingroup$

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)

I feel like I'm going in circles... any suggestions?

  • 0
    $n + \log(n) = c*n$ is not true for any $c$ if $n$ varies2012-09-14

2 Answers 2

1

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

  • 0
    fixed the inequalities, thanks.2012-09-14
2

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

  • 0
    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.2012-09-15