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 positive constant.) You should assume that f and g are nondecreasing and always bigger than

Answer 1

The complexity of function or an algorithm = f(n) is of the order of g(n).
         f(n)  =  O( g(n) )

f(n) * Log2 ( f(n)* c)
   = f(n) [ Log2 f(n) + Log2 c ]
   = f(n) Log2 f(n)  +  Log2 c  * f(n)
   = O(g(n)) * Log2 (O(g(n)) )  + Log2 c * O(g(n))
   = O( g(n) * Log2 (g(n) )
True.
 
 Here Log2 c is a constant...  where as O (Log2 g(n) ) is assumed to be varying with n.  That does not depend on constant c.