Trovare un O-grande di log(n^n)

[ramy1989]

Devo trovare un O-grande di log(n^n).
Siccome il logaritmo è in base dieci, per n che tende a infinito log n si può approssimare ad n, quindi risulta che:
log(n^n)=O(n^n) , è giusto ?

[hamming_burst]

Ciao,
sì certo $log_{10}(n^n) in O(n^n)$ ma mi sembra un po' assurdo attribuire una complessità tanto alta, addirittura super-esponeziale...

Secondo te con le proprietà dei logaritmi:

$log_{10}(n^n) = ?$

nota: $=$ inteso come equivalenza, non appartenenza all'insieme $O()$.

[ramy1989]

nlogn ?

[hamming_burst]

"ramy1989":nlogn ?

eh certo

Perciò, qual è la classe polinomiale "più vicina" che contiene $nlog(n)$?
Poi basta che lo dimostri con uno dei vari metodi, quello del limite all'infinito è più veloce

[ramy1989]

Direi che è risolto, C(n)=nlogn , non c'è bisogno di andare avanti vero ?

[ciampax]

Io direi che $\log(n^n)=O(n^2)$ (se proprio vogliamo usare una stima polinomiale). Infatti $\log n^n=n\cdot \log n$. Inoltre, per qualsiasi $\alpha>0$ è noto che $\lim_{n\to+\infty}\frac{\log n}{n^\alpha}=0$.