Chapter 4, Problem 21R

Explanation of Solution

Given:

It is given that if $p\left(n\right)$ is a polynomial in $n$, then $logp\left(n\right)$ is $O\left(logn\right)$.

Proof:

Let us assume that the polynomial function be $p\left(n\right)=a_m{n}^m+an{}^{m-1}+\mathrm{...}+a_{1}n+a_0$.

The above function can be written as:

$p(n)<\max \left\{\left|a_m\right|,\left|a_{m-1}\right|,\mathrm{...},\left|a_0\right|\right\}\left(m+1\right)+n^m$        (1)

Now, take logarithm on both the sides of the Equation (1). Then, Equation (1) becomes as follows:

$\log p(n)<\log (\max \{\left|a_m\right|,\left|a_{m-1}\right|,\mathrm{}$