Search code examples
algorithmmathtime-complexitylittle-o

Proving if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n))

So I'm struggling with proving (or disproving) the above question. I feel like it is true, but I'm not sure how to show it.

Again, the question is if g(n) is o(f(n)), then f(n) + g(n) is Theta(f(n))

Note, that is a little-o, not a big-o!!!

So far, I've managed to (easily) show that:

g(n) = o(f(n)) -> g(n) < c*f(n)

Then g(n) + f(n) < (c+1)*f(n) -> (g(n) + f(n)) = O(f(n))

However, for showing Big Omega, I'm not sure what to do there.

Am I going about this right?

EDIT: Everyone provided great help, but I could only mark one. THANK YOU.

Solution

  • So far so good.

    For the next step, recall that in the best case, 0 <= g(n); this should get you a lower bound on g(n) + f(n).