patternMinor
Proof of $f(n) + ο(f(n)) = \Theta(f(n))$
Viewed 0 times
thetaproofstackoverflow
Problem
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
Solution
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)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)|}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))$.
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)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)|}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))$.
Context
StackExchange Computer Science Q#139048, answer score: 3
Revisions (0)
No revisions yet.