Nella notazione Theta che hai postato c'è un piccolo errore, hai messo un maggiore al posto di un minore (o viceversa). Ovviamente è:
codice:
0 <= c1*g(n) <= f(n) <= c2*g(n)
Quando hai una funzione, per verificare se appartene ad uno di questi insiemi di funzioni (O, Theta, Omega - in realtà ce ne sono anche altri due) basta che applichi la definizione e verifichi le disuguaglianze.
Data f(n) = 3n^2 + 10 ovviamente si vede ad occhio che è in O(n^2) ma devi dimostrarlo applicando la definizione, che è:
codice:
f(n) = O(g(n)) se esistono c > 0 t.c. f(n) <= c*g(n) per n sufficientemente grande
Quindi devi trovare i due valori di c ed n che rendono vera la seguente disequazione:
Che è:
codice:
3*n^2 + 10 <= c*n^2
Con c = 4 e n = 10:
codice:
3*10^2 + 10 <= 4*10^2
310 <= 400
Le due costanti trovate verificano la disequazione, quindi è dimostrato che f(n) appartiene a O(n^2).
In modo analogo dimostri il lower bound (ovviamente le costanti possono essere diverse). Per la notazione Theta, non serve rifare i calcoli, perché se una funzione è sia in O(g(n)) che in Omega(g(n)) allora è anche in Theta(g(n)).
Riguardo alle ultime due righe, è semplice dimostrare (come ho fatto sopra) che f(n) è in O(n^3). Ciò che però non puoi fare è verificare che f(n) sia in Omega(g(n)), di conseguenza non puoi affermare che f(n) sia in Theta(g(n)), perché come ho già detto il limite inferiore dovrebbe coincidere con quello superiore.
Rispondi quotando