Complessità algoritmica

[ncc17011]

Ciao,

potreste cortesemente controllare se ho risolto bene il seguente esercizio e se no, indicarmi dove ho sbagliato:

1) $3^n = O(3^(n+1))
2) $f(n) <= c * g(n)
3) $3^n <= c*3^(n+1)
4) $log_3 3^n <= c * log_3 3^(n+1)
5) $n <= (n+1) *c

che è vera, in quanto $(n+1) *c$ cresce più velocemente di $n$.

Grazie

[Luca.Lussardi]

Di solito quando si assegna un esercizio si da' il testo dell'esercizio stesso; personalmente non ho capito niente di quello che chiedi.

[ncc17011]

Ciao Luca,

si tratta di mostrare che $f(n)$ è compresa in $g(n)$. La O deriva dalla c.d. Big-O Notation e rappresenta il caso peggiore della crescita di una funzione.
Ora per capire se $f(n)$ è compresa, si verifica se $f(n)$ è minore o uguale a $g(n)$ moltiplicato per una costante. Poiché alla fine si verifica $n <= (n+1) *c $, si può affermare che $f(n)$ cresce più lentamente di $g(n)$ (salvo errori miei di calcolo) e che l'espressione è vera.

[Luca.Lussardi]

Se devi dimostrare che $3^n=O(3^(n+1))$ non serve tutto questo giro, basta osservare che $3^n=1/3 3^(n+1)$.

[ncc17011]

"Luca.Lussardi":Se devi dimostrare che $3^n=O(3^(n+1))$ non serve tutto questo giro, basta osservare che $3^n=1/3 3^(n+1)$.

o_O Ora sono io a non capire la tua semplificazione. Me la spieghi per favore?

[Luca.Lussardi]

Devi mostrare che $3^n=O(3^(n+1))$, e dunque che esiste $c>0$ tale che $(3^n)/3^(n+1) \le c$. Ma $(3^n)/3^(n+1)=1/3$, da cui $c=1/3$.

[ncc17011]

"Luca.Lussardi":Devi mostrare che $3^n=O(3^(n+1))$, e dunque che esiste $c>0$ tale che $(3^n)/3^(n+1) \le c$. Ma $(3^n)/3^(n+1)=1/3$, da cui $c=1/3$.

Quindi l'aver trovato $c>0$ determina che è quindi vero che $3^n = O(3^(n+1))$ ?. Io mi facevo sempre i giri per arrivare a delle funzioni dalle quali potevo evincere quale crescesse più in fretta.