2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Note that the constant implied by the big-O notation depends on $n$. $\endgroup$ – marty cohen Oct 6 '12 at 22:50
  • $\begingroup$ @martycohen Yes, for example when $g(x)=x^n$ we have to take a constant $\geq n$. $\endgroup$ – Davide Giraudo Oct 7 '12 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.