Как доказать, что ?

Это домашнее задание из книги Уди Манбера. Любой намек был бы хорош :)

Я должен показать, что:

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

Я попытался использовать теорему 3.1 книги:

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

Substituing:

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

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

Спасибо за любую помощь.

Делайте то, что вы сделали, но пусть ... это должно сделать это, верно?$a = (3^{0.2})$

Причина того, что вы не работали, заключается в следующем. Биг-о-о не ограничен; в то время как логарифм до пятого действительно является большим ой линейных функций, он также является большим ой пятой корневой функции. Вам нужен этот сильный результат (который вы можете также получить из теоремы), чтобы делать то, что вы делаете.

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

$\alpha$