Notazione asintotica

[peppe89ct]

secondo voi quale di questa non è vera?

[tex]2^{log_4 (n)}=Theta(n^2)[/tex][/list:u:1g87pyoy]

[tex]4^{log_2 (n)}=Omega(n^2)[/tex][/list:u:1g87pyoy]

[tex]2^{log_3 (n)}=O(n)[/tex][/list:u:1g87pyoy]

[tex]3^{log_2 (n)}=Omega(n)[/tex][/list:u:1g87pyoy]

Secondo me la prima svolgendo la disequazione......Per voi(che sicuramente siete più esperti di me ) è giusta???

[apatriarca]

Direi che la prima è falsa come dici. Hai infatti che
\[ 2^{\log_4 n} = 2^{(\log_2 n)/2} = \sqrt{n} \notin \Theta(n^2). \]
Le altre, ad una rapida occhiata, mi sembrerebbero vere.

[peppe89ct]

"apatriarca":Direi che la prima è falsa come dici. Hai infatti che
\[ 2^{\log_4 n} = 2^{(\log_2 n)/2} = \sqrt{n} \notin \Theta(n^2). \]
Le altre, ad una rapida occhiata, mi sembrerebbero vere.

Scusa puoi mostrarmi i passi algebrici??

[apatriarca]

Ho fatto praticamente tutti i passaggi.. Sono semplici applicazioni delle proprietà dei logaritmi (cambiamento di base, la regola che lega l'esponente ai coefficienti del logaritmo e la definizione di logaritmo).

[peppe89ct]

Grazie mille!!!