Comment prouver que

C'est une question de devoirs du livre d'Udi Manber. Tout indice serait bien :)

Je dois montrer que:

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

J'ai essayé d'utiliser le théorème 3.1 du livre:

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

Substitution:

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

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

Merci pour toute aide.

asymptotics landau-notation mathematical-analysis Andre Resende
la source

Quelles méthodes pouvez-vous utiliser? jetez un oeil à cette réponse, elle pourrait vous donner quelques idées. Ici aussi , il y a beaucoup d'informations utiles.

Ran G.

@A sonné. si cela doit être fermé à la lumière de la question liée

Suresh

@Suresh, je ne suis pas sûr. Je crains que si nous ne le faisons pas, nous serions inondés de telles questions (qui devraient peut-être mieux convenir aux mathématiques ). Mais c'est une question valable.

Ran G.

@A sonné. J'ai essayé d'appliquer les limites, mais sans succès ..

Andre Resende

@RanG .: math.SE est déjà inondé de ces questions, principalement des "algorithmes" balisés.

Louis

Réponses:

Faites ce que vous avez fait, mais laissez ... cela devrait le faire, non? $a = (3^{0.2})$

La raison pour laquelle ce que vous avez fait n'a pas fonctionné est la suivante. La limite du grand oh n'est pas serrée; alors que le logarithme au cinquième est en effet un grand oh de fonctions linéaires, il est également un grand oh de la cinquième fonction racine. Vous avez besoin de ce résultat plus fort (que vous pouvez également obtenir du théorème) pour faire ce que vous faites.

Patrick87
la source

En fait, pour tout ,

ϵ > 0

$\epsilon >0$

n \log^{c} n = O (n^{1 + ϵ})

$n \log^c n = O(n^{1+\epsilon})$

Ran G.

@A sonné. Oui, c'est une conséquence directe du théorème.

Patrick87

@AndreResende Si ma réponse vous a aidé à résoudre votre problème et que cela a du sens, vous pouvez "accepter" en utilisant la coche verte. Cela aide les autres à voir ce qui a fonctionné pour vous et pourrait vous aider à obtenir plus d'aide à l'avenir. Bien sûr, si vous souhaitez d'autres réponses, attendez.

Patrick87

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

$\alpha$

Artem Kaznatcheev
la source