Suppose that p(x) is any polynomial in x with positive coefficients. Show that log(p(x))∈O(logx).

Question

Suppose that p(x) is any polynomial in x with positive coefficients. Show that $log(p(x))∈O(log\ x)$.

My professor posed this question in class today, and I'm not sure how to go about proving it. It's very interesting though!

Answer 1

Let the maximum degree in the polynomial be $m$. Then, since $p(x)$ is a polynomial, it can be expressed in:

$p(x) = \sum_{0 \le i \le m} a_i x^i$.

Where each $a_i$ is a constant. Let $a_\text{max}$ be the value amongst all $a_i$ with maximum absolute value (that is, for every $i$, $|a_\text{max}| \ge |a_i|$). Then we have

\begin{alignat*}{2} \log(p(x)) & = \log(\sum_{0 \le i \le m} a_i x^i) \\ & \le \log(\sum_{0 \le i \le m} |a_\text{max}| |x|^i) \\ & \le \log(\sum_{0 \le i \le m} |a_\text{max}| |x|^m) \\ & = \log(m \cdot |a_\text{max}| \cdot |x|^m) \\ & = \log(m) + \log(|a_\text{max}|) + \log(|x|^m) \\ & = \log(m) + \log(|a_\text{max}|) + m\log(|x|) \end{alignat*}

Since both $a_\text{max}$ and $m$ are constants, it follows that $\log(p(x)) = O(\log x)$.