Prove that $\log f(n)$ is $O(\log n)$.

Question

If $f(n)$ is any polynomial in n with positive coefficients, how could I prove that $\log f(n)$ is $O(\log n)$? I've been having trouble how to do this for a while now.

Answer 1

Hint: Let $d$ be the degree of $f$, and let $M$ be an upper bound on the coefficients. Then $$f(n)\le (d+1)(M)(n^d).$$ Now take the logarithm.

Answer 2

Here's a very quick-and-dirty solution. Since we know $f(n)$ is a polynomial in $n$, we have $f(n)=O(n^m)$ for some $m\in N$. This is to say there's a positive constant $c: f(n) \leq cn^m$ for sufficiently large $n$. Taking logarithms on both sides, we have $\log f(n) \leq \log(c) + m \log(n)$; we can weaken this to $\log f(n) \leq (m+c) \log (n)$. This proves your result.

Answer 3

First of all, $f(n) = O(n^p)$ where $p$ - degree $f$, it means that $\frac{f(n)}{n^p}\to C$ as $n\to\infty$.

Then $\log(\frac{f(n)}{n^p})\to \log(C)$ and $\log(f(n)) - p\log(n)\to \log(C)$, dividing by $\log(n)$ have $\frac{\log(f(n))}{\log(n)} \to p$. As $p$ is constant we obtain $\log(f(n)) = O(\log(n))$