1
$\begingroup$

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)?

$\endgroup$

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.