Take the 2-minute tour ×
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.

my assignment is to (dis)prove the following

 f(n)+o(f(n))=Θ(f(n))

for example:

for all n >= n', n + log(n) = c*n

so far I have:

for all n >= n', f(n)=o(g(n)) <-> f(n) < c*g(n)    //definition of o
for all n >= n', f(n)=Θ(g(n)) <-> f(n) = c*g(n)    //definition of Θ
given g(n)=o(f(n))
f(n)+o(f(n))=f(n)+g(n)
f(n)=c*f(n)
g(n)<c*f(n)

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

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

2 Answers

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

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

share|improve this answer
    
fixed the inequalities, thanks. –  Ocasta Eshu Sep 14 '12 at 23:46
add comment

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|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

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.