Search code examples
algorithmmathproofbig-o

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

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

Solution

  • 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) = 2n. Is f(n) really Ω(f(n) + g(n)) here?

    Hope this helps!