# Big O proof

• Feb 15th 2010, 01:28 PM
centenial
Big O proof
I'm having trouble with this proof:

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

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

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

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

Any help would be much appreciated,
• Feb 15th 2010, 06:13 PM
centenial
I've been thinking about it more. Would this be sufficient?

We can approximate $p(n)$ to be $n^k$, where $k$ is the highest degree in $p(n)$. We notice that $p(n)$ is $O(n^k)$. Next, we observe that $\log{n^k} = k\log{n}$. Therefore, $\log{p(n)} = k\log{n}$, so $\log{p(n)} = O(\log{n})$.
• Feb 15th 2010, 09:12 PM
Drexel28
Quote:

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

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

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

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

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

Any help would be much appreciated,

We know that there exists some $C$ and some $N$ such that $N\leqslant n\implies p(n)\leqslant Cn^{k}$. And clearly there exists some $N'$ such that $N'\leqslant n\implies Cn^{k}\leqslant n^{k+1}$ and so $N'\leqslant n\implies p(n)\leqslant n^{k+1}\implies \log p(n)\leqslant (k+1)\log n$