Prove or disprove each of the following claims where fn and

Prove or disprove each of the following claims, where f(n) and g(n) are functions on positive values. (a) f(n) = O(g(n)) implies g(n) = Ohm(f(n)) (b) f(n) = O(g(n)) implies 2^f(n) = O(2^g(n)) (c) f(n) = O((f(n))^2)

Solution

Big-O is the notation for tightest upper bound..and Big-Omega is tigtest lower bound...

p implies q, means if p is true, q must also be true..

a) f(n) = O(g(n)) implies g(n) = Omenga(f(n)

This statement is false..

if tightest upperbound for f(n) is g(n)... means f(n) < k*g(n).. k some constant..

here some particular constant k making the g(n) greater than f(n)...

there some constants k, where k*g(n) <f(n)

hence f(n) will not be the tightest lower bound

then tightest lower bound for g(n) would be g(n) itself not f(n) .. k.g(n)<g(n).

so , this fails..

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

This statement is true..

if tightest upperbound for f(n) is g(n)... means f(n) < k*g(n).. k some constant..

here some particular constant k, making the g(n) greater than f(n)...

so..

f(n)<k*g(n)

apply log both sides..

log(f(n))<log(k*g(n))

we have log n = k//then n = 2^k

apply this

2^(f(n))<2^(k*g(n))

by this..

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

hence this is true..

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

This statment is false..

Big-O :denotes the tightest upper bound..

it lies on the same degree of the function...f(n)

powering f(n) by 2, increases the degree of function f(n)..

means f(n)^2 is the only the upper bound for the f(n), not tightest upper bound..