Crescita asintotica delle funzioni

[Darèios89]

Lo schema che conosco io, delle funzioni elencate in ordine di crescita è:

[tex]c, \log(n), n, n\log(n), n^b, b^n, n!, n^n[/tex]

Se per esempio devo confrontare [tex]n^{\log_2(3)}[/tex] con [tex]n\log(n)[/tex]

Io direi che la seconda è più grande asintoticamente, o sbaglio?

[pater46]

Beh no.. A parte il fatto che, come dici tu, hai una sequenza ben definita per gli ordini di infinito, se consideri il loro rapporto:

$lim_{n} n^\alpha/(nlogn) = lim_{n} n^(alpha-1)/logn$

noti subito che il numeratore diverge molto più rapidamente, fintanto che $alpha > 1$ ( nel tuo caso $log_2 3 \approx 1.58 > 1$ )

[Darèios89]

Azzz vero Pater!!!!
Confronto asintotico
Grazie tante.

[pater46]

A chi non è mai capitato di confondersi su queste cose! Alla prox