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

algorithm big-o analysis notation
csnate picture csnate · Oct 9, 2012 · Viewed 17.1k times · Source

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.

Answer

amit picture amit · Oct 9, 2012 
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.

Related questions

Reccurrence T(n) = T(n^(1/2)) + 1

I've been looking at this reccurrence and wanted to check if I was taking the right approach. T(n) = T(n^(1/2)) + 1 = T(n^(1/4)) + 1 + 1 = T(n^(1/8)) + 1 + 1 + 1 ... = 1 + 1 + 1 + ... + 1 (a total of rad n times) = n^(1/2) So the answer would come to theta bound …

Read More
Why is the constant always dropped from big O analysis?

I'm trying to understand a particular aspect of Big O analysis in the context of running programs on a PC. Suppose I have an algorithm that has a performance of O(n + 2). Here if n gets really large the 2 becomes …

Read More
Meaning of lg * N in Algorithmic Analysis

I'm currently reading about algorithmic analysis and I read that a certain algorithm (weighted quick union with path compression) is of order N + M lg * N. Apparently though this is linear because lg * N is a constant in this universe. …

Read More