You are given functions f and g such that f(n)=O(g(n)). Is f(n)∗log2(f(n)c)=O(g(n)∗log2(g(n))) ? (Here c is some constant 0. You can assume that f and g are always bigger than 1.

a) true
b)false
c)depends on c
d) depends on f and g

Question

You are given functions f and g such that f(n)=O(g(n)). Is f(n)∗log2(f(n)c)=O(g(n)∗log2(g(n))) ? (Here c is some constant >0. You can assume that f and g are always bigger than 1.

a) true
b)false
c)depends on c
d) depends on f and g

anonymous · Answer

I think could go this way, but not sure:
f(n)=O(g(n)) means |f(n)|<= M |g(n)|  or |f(n)|/|g(n)| <= M
so you have to prove, given that f(n)=O(g(n)), that  |f(n)∗log2(f(n)c)|/|g(n)∗log2(g(n))| <= N
 |f(n)∗log2(f(n)c)|/|g(n)∗log2(g(n))| <= M|log2f(n)c)|/|log2(g(n))| = 
=M log2|(f(n)c -g(n))| <= M log2 (|M|g(n)|c - g(n)|). 
So i think it depends on c.