Asymptotic Analysis For each of the following statements dec

Asymptotic Analysis For each of the following statements, decide whether it is always true, never true, or sometimes true for asymptotically nonnegative functions f and g. If it is always true or never true, give a proof. If it is sometimes true, give one example for which itis true, and one for which it is false.

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

(b) f(n) = (g(n)) and f(n) = O(g(n))

(c) f(n) = O(g(n)) implies 2^f(n) = O(2^g(n)

Please show proof as asked in the question!

Solution

The first is not true : from this f(n) O(g(n)) it does not follow this: f(n) = w(g(n)). The two functions might intersect at some point and then slap places, the other becoming bigger (if I use simple words).

The function they chose is just this case: for n <= 1 the first f(n) > g(n) and there exist ns for which g(n) > f(n) (e.g pi

I think n*sin(n) just shows that it is a function which keeps getting larger & smaller than f(n) = 1for subsequent values of n even for all choices of a constant multiplier used for defining Big O & thus f(n) O(g(n)) and g(n) O(f(n))

A Naively chosen function like g(n) = 2*sin(n) won\'t do good here. One might think that this would also keep alternating around f(n) = 1 , but g(n) = O(f(n)) : M*f(n) > g(n) for M = 3 etc