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

Answer 1

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 it depends on c hope it works