is $f(x)$ in big-$O$ of $g(x)$ assuming the following?

Question

Assuming that: $f(n)=O(g(n))$ and $f(n)$ and $g(n)$ are nondecreasing and always bigger than 1

Is the following necessarily true?

$$f(n)\log_2(f(n)^c)=O(g(n)\log_2(g(n)))$$

And also, could you explain why? Thanks.

Answer 1

If you can prove that $\log f(n) = O(\log g(n))$ you are done.

Letting $C_0$ be such that $f(n)< C_0 \cdot g(n)$ for all $n$.

Then $\log f(n) < \log C_0+ \log g(n)$

Let $D=\log g(1)$. Then $$\log C_0 = \frac{C_0}{D} \log g(1) \leq \frac{C_0}{D} \log g(n)$$

This means that $\log f(n) < \left(\frac{\log C_0}{D} +1\right)\log g(n)$

(We need $g(n)$ non-decreasing for that last inequality. We really don't need that strong a condition. I believe all you need is $\liminf_{n\to\infty}g(n)>1$.)

So $$f(n)\log f(n)< C_0 g(n) \left(\frac{\log C_0}{D}+1\right)\log g(n)= Fg(n)\log g(n)$$

where $F=C_0\left(\frac{\log C_0}{D}+1\right)$.

Note, we can always pick $C_0>1$, so we don't need to worry about the sign of $\log C_0$.

Finally, the constant $c$ is irrelevant, since $f(n)\log f(n)^c=cf(n)\log f(n)<cF\cdot g(n)\log n$.

Note that you need $\liminf g(n) >1$. For example, if $g(n)=1+\frac{1}{n}$ and $f(n)=2$, then $f(n)=O(g(n))$, but $f(n)\log_2 f(n)=2$ and $g(n)\log_2 g(n)=O(\frac{1}{n})$