Significato di polinomialmente più grande o più piccolo nel contesto del metodo principale

Question

Sto studiando il metodo principale per risolvere le recidive e ho un background matematico un po 'decente, ma ho difficoltà a capire il concetto di $ n^{ log_ba} $ essendo polinomialmente più piccolo o più grande di $ f (n) $.

Ciò che voglio dire è $ n^{ log_ba} $ essendo polinomialmente più grande o più piccolo della funzione $ f (n) $ Per le relazioni di ricorrenza della forma: $ T (n) = at ( dffrac nb) + f (n) $.

Il caso 1 è il caso in cui $ n^{ log_ba} $ è polinomia più grande di $ f (n) $.
Il caso 2 è il caso in cui $ n^{ log_ba} $ è uguale a $ f (n) $.
Il caso 3 è il caso in cui $ n^{ log_ba} $ è polinomia più piccolo di $ f (n) $.

Come lo definisce il mio libro, affinché il caso 1 si applichi $ n^{ log_ba- epsilon} $ per alcuni $ epsilon> 0 $ deve essere più grande di $ f (n) $. in altre parole, $ n^c> f (n) $ dove $ c < log_ba $.

Allo stesso modo, per il caso 3 da applicare $ n^{ log_ba+ epsilon} $ per alcuni $ epsilon> 0 $ deve essere più piccolo di $ f (n) $ o in altre parole $ n^c <f (n) $ dove $ c> log_ba $.

Un altro modo per pensare di sottrarre $ epsilon $ è pensare $ dfrac {n^{ log_ba}} {n^e} $ per alcuni $ epsilon> 0 $.

e un altro modo di pensare all'aggiunta del $ epsilon $ è pensare $ n^{ log_ba}*n^ epsilon $ per alcuni $ epsilon> 0 $.

Nelle mie diapositive di classe sul metodo principale il primo esempio utilizza la ricorrenza $ T (n) = 4t ( dffrac n2) + 1 $ e suggerisce la possibilità che il caso 1 si applica. $ n^{ log_ba} $ sarebbe $ n^2 $ e $ f (n) $ sarebbe 1.

La diapositiva lo sottolinea $ f (n) $ non è polinomia più piccolo di $ n^2 $.

Non lo capisco completamente perché se prendi $ 0> epsilon> 1 $ come $1/2$ Per esempio.

Puoi quindi sottrarre questo epsilon da $ n^2 $ E lo avresti fatto $ n^{1.5} $ che sarebbe ancora maggiore di $ f (n) = 1 $ per ogni $ n> 1 $.

Quindi, come è questo un esempio di essere polinomialmente più piccolo?

Inoltre, la diapositiva che lo spiega $ f (n) $ In questo esempio non è polinomialmente più piccolo, lo indica $ T (n) = 4t ( dfrac n2) + dfrac {n^2} { log n} $ non funziona

Ma perché avrebbero tentato di dividere $ n^2 $ di $ log n $ innanzitutto? Ottengo la divisione equivale a sottrarre un $ epsilon $ dall'esponente di $ n $, ma perché $ log n $, qual è il significato?

*EDIT: Risposta del mio professore:

Ad esempio (supponendo che tutti i numeri siano positivi per mantenerlo sjmple), l'idea è che per qualsiasi numero $ p $ e $ Q $, Se $ q> p $, $ (n^p)*log (n) <n^q $ asintoticamente, non importa quanto vicino $ p $ il numero $ Q $ è.

Così $ n^p*log (n) $ non è polinomia più grande di $ n^p $ perché per qualsiasi $ q> p $, alla fine sarà più piccolo allora $ n^q $