Question

Write always true, never true, or sometimes true for each and give a proof (using the definitions of O(), Ω(), o()...). If it is sometimes true, give cases where it is, and cases where it isn't.

If f(n) = O(g(n)), then 2^f(n) = O 2^g(n)

If f(n) = O(g(n)), then g(n) − f(n) = Ω(g(n)).

If f(n) = o(g(n)), then g(n) − f(n) = Ω(g(n)).

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

b)

It is not true for example

f(n)=2n and g(n)=n

2^(f(n))=2^(2n)

2^g(n)=2^n

But,

2^(2n) is not equal to O(2^n)

c)

Since

f(n)<=c*g(n) using big O definition

So,

g(n)-f(n)>=g(n)-c*g(n)=g(n)*(1-c)

So, we can write that

g(n)-f(n)>=c1*g(n)

where c1=1-c

So, we have found a constant.

So, it is always true

d)

Since

f(n)<c*g(n) using definition of little o

So,

g(n)-f(n)>g(n)-c*(g(n))

So,

g(n)-f(n)>g(n)*(1-c)

So, we can say that

g(n)-f(n)>=c2*g(n)

So, this is also true

Kindly revert for any queries

Thanks.