I'm working through proof of $f(n) + o(f(n)) = \theta (f(n))$ and I came across a part in the proof that I am having trouble understanding.

We let $f(n)$ and $g(n)$ be asymptotically positive functions and assume $g(n) = o(f(n))$. In the proof, it states that since we know that $ f(n) + g(n) ≥ f(n)$ for all n, we can conclude that $f(n) + g(n) = \Omega((f(n))$. We can also conclude similarly that $f(n) + g(n) ≤ 2 f(n)$. Therefore $f(n) + g(n) = O(f(n))$. I am having trouble understanding why it is the case that $f(n) + g(n) = \Omega((f(n))$ and $f(n) + g(n) = O(f(n))$ would be true. How is it that we can prove that the tight-lower bound is specifically when we add $g(n)$ to $f(n)$? What is it that we are exactly concluding from the value of g(n)?


Your Answer

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

Browse other questions tagged or ask your own question.