[KatherineR]

Buenas tardes. Quisiera saber como hacer esta demostración. No se me ocurre como :

Muestre que si \( p(n) \) tiene complejidad polinomial en \( n \), entonces \( log(p(n)) \) es \( O(log(n)). \)

Muchas Gracias

[martiniano]

Hola.

Si \[ p(n)  \] es un polinomio de grado \[ m \] entoces se puede escribir como \[ p(n) =a\cdot{n^m+q(n) } \] donde \[ q(n)  \] es un polinomio de grado \[ m-1 \].

Al ser finito y no nulo el siguiente límite:

\[ \lim\displaystyle\frac{\log(p(n))} {\log n}=   \lim\displaystyle\frac{\log(a\cdot{n^m+q(n) }) } {\log n}= \lim\displaystyle\frac{\log(a\cdot{n^m}\left(1+\displaystyle\frac{q(n) }{a\cdot{n^m}}\right)) } {\log n}  =\displaystyle\frac{\log a+m\log(n) }{\log(n) }=m \]

Tienes lo que dice el enunciado.

Un saludo.