¿Cómo demostrar que

Esta es una pregunta de tarea del libro de Udi Manber. Cualquier pista sería buena :)

Debo demostrar que:

$n(\log_3(n))^5 = O(n^{1.2})$

Intenté usar el Teorema 3.1 del libro:

c > 0 a > $f(n)^c = O(a^{f(n)})$ (para , )$c > 0$$a > 1$

Sustituyendo:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n)$

pero$n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Gracias por cualquier ayuda.

Haz lo que hiciste, pero deja que ... eso debería hacerlo, ¿verdad?$a = (3^{0.2})$

La razón por la que lo que hiciste no funcionó es la siguiente. El gran límite no es apretado; mientras que el logaritmo al quinto es de hecho grande-oh de funciones lineales, también es grande oh de la quinta función raíz. Necesita este resultado más fuerte (que también puede obtener del teorema) para hacer lo que está haciendo.

$(\log_3(n))^5$$O(n^{0.2})$$\log_3(n)$$O(n^{0.04})$

Si desea formalizar la última oración, puede usar el teorema 3 con un suficientemente pequeño como @RanG menciona en el comentario sobre la respuesta de @ Patrick87.$\alpha$