Given fn and gn are nondecreasing prove maxfngn fn gn and

Given f(n) and g(n) are non-decreasing, prove:

               max(f(n),g(n)) = (f(n) + g(n))

and then prove:

               max(f(n),g(n)) = (f(n) + g(n))

Solution

Given f(n) and g(n) are non-decreasing

prove: max(f(n),g(n)) = (f(n) + g(n)) and max(f(n),g(n)) = (f(n) + g(n))

solution:

letf(n) 0 and g(n) 0 wheren n0

therefore f(n) + g(n) f(n) 0............. eq.(1)

and also f(n) + g(n) g(n) 0............. eq.(2)

adding eq.(1) and eq. (2)

f(n) + g(n) max(f(n) + g(n) ) for n n0

this proves :

max ( f(n), g(n) ) c ( f(n) + g(n)) for n n0

when c=1

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

or we can say that

2max ( f(n) , g(n) ) ( g(n) + f(n) )

or max ( f(n) , g(n) ) 1/2 ( g(n) + f(n) ) for all n n0.

Therefore max( f(n) , g(n) ) = ( g(n) + f(n) ) with constant c = 1/2