Signification de polynomialement plus grand ou plus petit dans le contexte de la méthode maître

Question

J'étudie la méthode maître pour résoudre les récidives et j'ai un contexte mathématique quelque peu décent, mais j'ai du mal à comprendre le concept de $ n ^ { log_ba} $ étant polynomialement plus petit ou plus grand que $ f (n) $.

Ce que je veux dire est $ n ^ { log_ba} $ être polynomialement plus grand ou plus petit que la fonction $ f (n) $ Pour les relations de récidive de la forme: $ T (n) = à ( dfrac nb) + f (n) $.

Le cas 1 est le cas dans lequel $ n ^ { log_ba} $ est polynomialement plus grand que $ f (n) $.
Le cas 2 est le cas dans lequel $ n ^ { log_ba} $ est égal à $ f (n) $.
Le cas 3 est le cas dans lequel $ n ^ { log_ba} $ est polynomialement plus petit que $ f (n) $.

Comme mon livre le définit, pour que le cas 1 s'applique $ n ^ { log_ba- epsilon} $ pour certains $ epsilon> 0 $ doit être plus grand que $ f (n) $. autrement dit, $ n ^ c> f (n) $ où $ c < log_ba $.

De même, pour que le cas 3 s'applique $ n ^ { log_ba + epsilon} $ pour certains $ epsilon> 0 $ doit être plus petit que $ f (n) $ ou en d'autres termes $ n ^ c <f (n) $ où $ c> log_ba $.

Une autre façon de penser à soustraire $ epsilon $ est de penser à $ dfrac {n ^ { log_ba}} {n ^ e} $ pour certains $ epsilon> 0 $.

et une autre façon de penser à l'ajout du $ epsilon $ est de penser à $ n ^ { log_ba} * n ^ epsilon $ pour certains $ epsilon> 0 $.

Dans ma classe diapositives sur la méthode maître, le premier exemple utilise la récidive $ T (n) = 4t ( dfrac n2) + 1 $ et suggère la possibilité que le cas 1 s'applique. $ n ^ { log_ba} $ serait $ n ^ 2 $ et $ f (n) $ serait 1.

La diapositive souligne que $ f (n) $ n'est pas polynomialement plus petit que $ n ^ 2 $.

Je ne comprends pas complètement cela parce que si vous prenez 0 0> epsilon> 1 $ tel que $1/2$ par exemple.

Vous pouvez ensuite soustraire cet epsilon de $ n ^ 2 $ Et tu aurais $ n ^ {1.5} $ qui serait encore plus grand que $ f (n) = 1 $ pour toute $ n> 1 $.

Alors, comment n'est-ce pas un exemple d'être polynomialement plus petit?

De plus, la diapositive qui explique que $ f (n) $ dans cet exemple n'est pas polynomialement plus petit, indique que $ T (n) = 4t ( dfrac n2) + dfrac {n ^ 2} { log n} $ ne fonctionne pas

Mais pourquoi auraient-ils tenté de diviser $ n ^ 2 $ par $ log n $ en premier lieu? J'obtiens que la division équivaut à soustraire un $ epsilon $ de l'exposant de $ n $, mais pourquoi $ log n $, quelle est la signification?

* Modifier: la réponse de mon professeur:

À titre d'exemple (en supposant que tous les nombres sont positifs pour le garder sjmple), l'idée est que pour tout nombre $ p $ et $ q $, si $ q> p $, $ (n ^ p) * log (n) <n ^ q $ asymptotiquement, peu importe à quel point $ p $ le nombre $ q $ est.

Alors $ n ^ p * log (n) $ n'est pas polynomialement plus grand que $ n ^ p $ Parce que pour tout $ q> p $, finalement ce sera plus petit alors $ n ^ q $