# Show $f(n)\log f(n)^c=O(g(n)\log g(n))$

You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Show that $f(n)\log_2(f(n)^c)=O(g(n)\log_2(g(n)))$. (Here $c$ is some positive constant.) You should assume that $f$ and $g$ are nondecreasing and always bigger than 1.

My solution: There exists $c_1$ such that $f \leq c_1 g$. Note that all $\log$ functions are base 2 throughout.

We have that $f \log(f^c) \le c_1 c g \log(c_1g) = c_1 c g \log(c_1) + c_1 c g \log(g)$.

Let expression $(*)$ be as follows:

$(*) \quad c_1 c g \log(c_1) + c_1 c g \log(g) \le c_2 g \log(g)$ for some $c_2 > 0$.

Then $(*)$ holds iff $c_1 c g \log(c_1) < 0$ iff $0 \leq c_1 \leq 1$.

Now put $c_2 = c_1 c$, then:

$c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$ iff $c_2 / c > 1$.

Therefore, we require than $c_2 > c$, which we cannot guarantee as we have already fixed $c_2 = c_1 c$.

What choice of $c_2$ would guarantee that $c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$?

I am looking for a formal argument.

An essential hint: "Assume that f and g are nondecreasing". That is essential. Without it the statement is false, for example $f (n) = 2$ and $g = 1 + 2^{-n}$, where log f (n) = 1 and log g (n) ≈ $2^{-n}$.
f (n) = O (g (n)) means "there are $N, c > 0$ so that we have $f (n) ≤ c·g (n)$ for $n ≥ N$". So there are $N, c > 0$ so that $\log f (n) ≤ c + \log g (n)$ for $n ≥ N$. Now we need to somehow relate c and $\log g (n)$. We have $c = (c \div \log g (N)) · \log g (N) ≤ (c \div \log g (N)) · \log g (n)$, because $g (n)$ is not decreasing. Therefore $\log f (n) ≤ (c \div \log g (N) + 1) · \log g (n)$, so we found a constant c' = (c / log g (N) + 1) such that $\log f (n) ≤ c' · \log g (n)$ for n ≥ N and that means $\log f (n) = O (\log (g (n))$.
• Thanks! If f and g were those functions, we are forced to choose $c_1>1$ so that $log(c_1)$ is positive and then the statement would not hold. Are there conditions on $c_1$ which hold due to the fact that f and g are non decreasing functions? May 24, 2017 at 14:16