Search code examples
algorithmbig-oanalysisnotation

Prove f(n) + g(n) is O(max(f(n),g(n)))

Hello I am having a bit of difficulty proving the following.

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

This makes logical sense, and by looking at this I can tell you that its correct but I'm having trouble coming up with a proof.

Here is what I have so far:

c * (max(f(n),g(n))) > f(n) + g(n) for n > N

But I'm not sure how to pick a c and N to fit the definition because I don't know what f(n) and g(n) are.

Any help is appreciated.

Solution 
  • f(n) + g(n) <= 2* max{f(n),g(n)} 
(for each n>0, assume f(n),g(n) are none-negative functions)

    Thus, for N=1, for all n>N: f(n) + g(n) <= 2*max{f(n),g(n)}, and we can say by definition of big O that f(n) + g(n) is in O(max{f(n),g(n)})

    So basically, we use N=1, c=2 for the formal proof by definition.