# Big-O of a polynomial within a logarithm.

I'm supposed to prove that :

For $g(x) = a_0+a_1 \cdot x+\cdots+a_n \cdot x^n$ a polynomial of degree $n$ where $n \ge 0$ and $a_n \ne 0$.

Prove that $\log|g(x)|$ is $O(\log(x))$.

I've been able to do it for specific polynomials, but I can't seem to prove this with a generic polynomial.

-

We can assume that $a_n=1$. Let $R$ such that if $|x|>R$ then $\left|\frac{a_0+\dots+a_{n-1}x^{n-1}}{x^n}\right|\leq 1$. Then $$\log|g(x)|=\log\left(|x|^n\left(\left|\frac{a_0+\dots+a_{n-1}x^{n-1}}{x^n}\right|\right)+1\right)\leq \log(|x|^n+1)\leq \log 2+n\log |x|$$ if $|x|>\max\{R,1\}$. This gives the wanted result, as if we assume $|x|\geq \max\{R,2\}$, we get $\log|g(x)|\leq (n+1)\log|x|$.
Note that the constant implied by the big-O notation depends on $n$. –  marty cohen Oct 6 '12 at 22:50
@martycohen Yes, for example when $g(x)=x^n$ we have to take a constant $\geq n$. –  Davide Giraudo Oct 7 '12 at 9:21