If f(n)=O(g(n)), then shouldn't f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) depend on the value of C?

Question

If f(n)=O(g(n)), then shouldn't f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) depend on the value of C?

Here C is a positive constant. According to me if C is large then the statement would become false and if c is small it'd be true. Hence the outcome is dependent on c.

I am taking a class on algorithms and this is one of the questions I was asked. According to me this should be dependent on constant c but the answer was wrong.

Answer 1

@Undefitied, By the definition of Big-Oh notation f(n) = O(g(n)) if and only if there exists a constant "c" and an N such that f(n) <= c*f(n) for all n > N. When we assert f(n) is "equal" to O(g(n)), we are not saying they are necessarily "equal" in algebraic terms. We are saying f(n) is bounded above by g(n). If f and g are nondecreasing and always bigger than one, and c is a positive constant, the proof given above by Mitch Wheat is true.

Answer 2

log(x^c)  = c * log(x)

So,

log2(f(n)^c) == c * log2(f(n))

Therefore,

f(n)∗log2(f(n)^c) = c * f(n) * log2(f(n))

                   = O(g(n)∗log2(g(n)))