Crescita delle funzioni

[ncc17011]

Salve,

studio informatica e tra l'altro devo provare affermazioni sulla complessità asintotica. Volevo cortesemente sapere se ho risolto bene questi particolari esercizi:

$2^(n+1) = O(n^2)

$O(g(n)) = {f(n):$ esistono delle costanti positive c e $n_0$ tali che $0<= f(n) <= c*g(n)$ per ogni $n >= n_0$}

quindi sviluppo:
1) $0<=2^[n+1] <= c*n^2
2) $2^[n+1] <= c*n^2
3) $log 2^[n+1] <= log c*n^2
4) $(n+1) log 2 <= c log n^2
5) $n+1 <= c * log n

n+1 cresce linearmente, mentre $c* log n$ è logaritmica, quindi 5) non è vero e intanto non è vero che $2^[n+1] = O(n^2).

Altro esercizio, stesso problema da risolvere:

$3^n = O(3^(n+1))
$ 0 <= 3^n <= c * 3^(n+1)
$ 3^n/3^(n+1) <= c
$ 0 <= 3^(n-(n+1)) <= c

Quindi vero che $3^n = O(3^(n+1)).

Sono risolti correttamente?

P.S.: è il mio primo post qui, ho trovato il sito mediante ricerca web e mi complimento per l'ottima riuscita. Penso sia molto importante avere più livelli e "tipi" di matematica in un unico sito.

[_Tipper]

Secondo me va bene.