1. ## Big O proof

I'm having trouble with this proof:

Show that if $\displaystyle p(n)$ is a polynomial in $\displaystyle n$, then $\displaystyle \log{p(n)}$ is $\displaystyle O(\log{n})$.

I'm given this definition for O(n):

$\displaystyle T(N) = O(f(N))$ if there are positive constants $\displaystyle c$ and $\displaystyle n_0$ such that $\displaystyle T(N) \leq cf(N)$ when $\displaystyle N \geq n_0$.

I'm not sure how to use it to arrive at the conclusion that $\displaystyle \log{p(n)} = O(\log{n})$. Wouldn't $\displaystyle \log{p(n)}$ always be greater than $\displaystyle \log{n}$?

Any help would be much appreciated,

2. I've been thinking about it more. Would this be sufficient?

We can approximate $\displaystyle p(n)$ to be $\displaystyle n^k$, where $\displaystyle k$ is the highest degree in $\displaystyle p(n)$. We notice that $\displaystyle p(n)$ is $\displaystyle O(n^k)$. Next, we observe that $\displaystyle \log{n^k} = k\log{n}$. Therefore, $\displaystyle \log{p(n)} = k\log{n}$, so $\displaystyle \log{p(n)} = O(\log{n})$.

3. Originally Posted by centenial
I'm having trouble with this proof:

Show that if $\displaystyle p(n)$ is a polynomial in $\displaystyle n$, then $\displaystyle \log{p(n)}$ is $\displaystyle O(\log{n})$.

I'm given this definition for O(n):

$\displaystyle T(N) = O(f(N))$ if there are positive constants $\displaystyle c$ and $\displaystyle n_0$ such that $\displaystyle T(N) \leq cf(N)$ when $\displaystyle N \geq n_0$.

I'm not sure how to use it to arrive at the conclusion that $\displaystyle \log{p(n)} = O(\log{n})$. Wouldn't $\displaystyle \log{p(n)}$ always be greater than $\displaystyle \log{n}$?

Any help would be much appreciated,
We know that there exists some $\displaystyle C$ and some $\displaystyle N$ such that $\displaystyle N\leqslant n\implies p(n)\leqslant Cn^{k}$. And clearly there exists some $\displaystyle N'$ such that $\displaystyle N'\leqslant n\implies Cn^{k}\leqslant n^{k+1}$ and so $\displaystyle N'\leqslant n\implies p(n)\leqslant n^{k+1}\implies \log p(n)\leqslant (k+1)\log n$