Como provar que

Esta é uma pergunta do dever de casa do livro de Udi Manber. Qualquer dica seria legal :)

Devo mostrar que:

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

Eu tentei usar o Teorema 3.1 do livro:

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

Substituindo:

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

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

Obrigado por qualquer ajuda.

Faça o que você fez, mas deixe ... que deve fazê-lo, certo?$a = (3^{0.2})$

A razão pela qual o que você fez não funcionou é a seguinte. O grande limite não é apertado; enquanto o logaritmo da quinta é de fato grande-oh de funções lineares, também é grande-oh da quinta função de raiz. Você precisa desse resultado mais forte (que você também pode obter do teorema) para fazer o que está fazendo.

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

$\alpha$