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

Question

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.

Answer 1

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}$.

The problem here is showing that f (n) = O (g (n)) implies log f (n) = O (log (g (n)). So how does "g is non-decreasing" help? Well, if n ≥ N then 1 < g (N) ≤ g (n) and 0 < log g (N) ≤ log g (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))$.