Let f n and gn be asymptotically nonnegative functions Using

Let f (n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Theta-notation, prove that max(f(n). g(n)) = Theta (f(n) + g (n)).

Solution

As we know that f(n)f(n)+g(n) and  g(n)f(n)+g(n)

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

Next note that f(n)+g(n) 2 max(f(n),g(n)). [By definition of Big O ]

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

max(f(n),g(n)) (f(n)+g(n)). [Again By the definition of Big ]

Hence, we get that

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

Thanks, let me know if there is any concern.