Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
$n + \log(n) = c*n$ is not true for any $c$ if $n$ varies – Henry Sep 14 '12 at 23:50
up vote 1 down vote accepted

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


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

share|cite|improve this answer
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))$.

share|cite|improve this answer
just using the notation from…, 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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