Showing f(n) = O(f(n) + g(n))?

Question

I was wondering what the proof for the following Big-O comparison is:

f(n) is O(f(n) + g(n)))

I understand that we could use:

f(n) ≤ constant * (f(n) + g(n))

But I don't know how to follow up.

What about the case where we replace big-O with big-Ω?

Answer 1

If you know that the function g(n) is nonnegative, then note that

f(n) ≤ f(n) + g(n) = 1 · (f(n) + g(n))

Given this, could you use the formal definition of big-O notation to show that f(n) = O(f(n) + g(n))?

If g(n) isn't necessarily nonnegative, then this result isn't necessarily true. For example, take f(n) = n and g(n) = -n. Then f(n) + g(n) = 0, and it's not true that f(n) = O(0).

As for the Ω case, are you sure this result is necessarily true? As a hint, try picking f(n) = n and g(n) = 2ⁿ. Is f(n) really Ω(f(n) + g(n)) here?

Hope this helps!