Can you please help me prove this? I am trying to set $o(f(n))= g(n)$ and then try to solve the equation $f(n) + g(n) = \Theta(f(n))$ but I don't know if it is the correct way, and if it is I don't know how to continue my solution. Thank you

  • 1
    $\begingroup$ Do you know that $f(n) + f(n) = \Theta(f(n))$? If so, you know that $f(n) + o(f(n)) \in O(f(n))$. Showing that $f(n) + o(f(n)) \in \Omega(f(n))$ should be easy, as $f(n) + o(f(n)) \geq f(n)$. $\endgroup$ Apr 18 at 21:34

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$.

Actually, in the same way you can easily prove also this stronger claim: $f(n)+O(f(n))=\Theta(f(n))$.

If $h(n)=o(f(n))$, then $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$, so there exists $n_0$ such that for all $n\geq n_0$ you have $h(n)\leq f(n)$ (actually, we can prove a stronger statemen, namely that for all $\varepsilon>0$, we have $h(n)< f(n)$, but here we not need it). This means that for all $n\geq n_0$ you also have $f(n)+h(n)\leq 2f(n)$, and then $f(n)+h(n)=O(f(n))$.

If you don't want to explicitely assume positiveness of the functions involved; I suggest to use limits (I like limits).

Remember that $f(n)=O(g(n))$ means $$ \limsup_{n\to+\infty} \frac{|f(n)|}{g(n)}<+\infty $$ while $f(n)=\Omega(g(n))$ means $$ \liminf_{n\to+\infty} \frac{|f(n)|}{g(n)}>0 $$ (use $|g(n)|$ instead of $g(n)$ if you want to take into account also negative functions). Notice that I'm not assuming that $\lim_{n\to+\infty} \frac{f(n)}{g(n)}$ exists, indeed $\liminf$ and $\limsup$ are used to deal with this case. Now, as above, let $h(n)$ be an $o(f(n))$, e.g. $\lim_{n\to+\infty} \frac{h(n)}{f(n)}=0$.

Finally $$ \limsup_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}<\limsup_{n\to+\infty} \frac{|f(n)|+|h(n)|}{|f(n)|}=\limsup_{n\to+\infty}\left( 1+\frac{|h(n)|}{|f(n)|}\right)=1<\infty $$ while $$ \liminf_{n\to+\infty} \frac{|f(n)+h(n)|}{|f(n)|}=\liminf_{n\to+\infty} |f(n)|\cdot\frac{\left|1+\frac{|h(n)|}{|f(n)|}\right|}{|f(n)|}\geq 1>0. $$ Also observe that in the first limit, we only need $\limsup_{n\to+\infty} \frac{|h(n)|}{|f(n)|}$ to be finite, so $h(n)$ can be also a $O(f(n))$.

  • $\begingroup$ Could you please explain it a little more? $\endgroup$
    – gianluigi
    Apr 17 at 19:12
  • $\begingroup$ I don't think it is a good idea to overload the definitions with the extra assumption that the functions are positive. The need for non-positive functions appear naturally, even if the final goal is to study functions that express number of operations in terms of size of the input. Just an opinion. Of course, anyone can do whatever they want with a definition, as long as it is said explicitly. $\endgroup$
    – plop
    Apr 17 at 19:16
  • $\begingroup$ The original statement doesn't need positivity of the functions involved. The statement that you said is stronger does require it. $\endgroup$
    – plop
    Apr 17 at 19:23
  • $\begingroup$ Well, I agree that in general $f$ can be (also definitively) negative, and that negative functions are interesting and useful. But if you write $O(f(n))$ (or $\Theta(f(n))$) then you are tacitly assuming that $f$ is definitely positive, see the wiki page, there's also the link to Landau original definition. $\endgroup$
    – user6530
    Apr 17 at 19:34

It's widely known, that $f=\Theta(g)$ we understand as "one direction" equality i.e. $f \in \Theta(g)$. But when we write something like $\Theta(f) = \Theta(g)$, then situation becomes slightly different: now it is equality between sets, so need proof in "two directions".

Equality $f+o(f)=\Theta(f)$ formally considered as equality between sets requires to be proved two facts $f+o(f) \subset \Theta(f)$ and $\Theta(f) \subset f+o(f) $. As first is shown in another answer, then let's concentrate on later:

Obviously $2f \in \Theta(f)$, but $2f \notin f+o(f)$, because $f \notin o(f)$.

So, we can write only $f+o(f) \subset \Theta(f)$ and as elaboration $f+o(f) \neq \Theta(f)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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