Dubbio notazioni asintotiche

[Slashino1]

Temo che qualcosa riguardo l'argomento in oggetto non mi è chiaro quindi vi espongo i miei dubbi con esempio sperando che qualcuno possa aiutarmi :
Secondo le definizioni che ho trovato sul libro e un pò da tutte le parti:
$ T(n) in O(f(n)) $ se $ EE c,n_0 : AA n>n_0 0 $ T(n) in \Omega(f(n) $ se $ EE c,n_0 : AA n>n_0 0 Inoltre vale la relazione $ T(n)=O(f_1(n)) +O(f_2(n)) -> T(n) in O(max(f_1(n),f_2(n)) $ $ iii $

Secondo la $i$ $1/2n^2=O(n^2)$ e $1/3n^3 = O(n^3) $ ( correggetemi se sbaglio ) .
Considero quindi $ T(n) = 1/2 n^2 + 1/3 n^3 $ che corrisponde a $ T(n)= O(n^2)+O(n^3) $ la quale per la $iii$ è $ O(max(n^2,n^3))=O(n^3)$; infatti presi due valori $c=100 , n_0=100 $ faccio vedere che vale la $i$.
Scegliendo però $ c= 1/100, $ a prescindere dal valore di $n_0$ scelto, ottengo $ 1/100n^3<1/3n^3+1/2n^2 $ che da conferma alla $ ii $ Dove sbaglio?

[hamming_burst]

Ciao,

"Slashino":
Secondo le definizioni che ho trovato sul libro e un pò da tutte le parti:
$ T(n) in O(f(n)) $ se $ EE c,n_0 : AA n>n_0 0 $ T(n) in \Omega(f(n) $ se $ EE c,n_0 : AA n>n_0 0

hai mescolato le definizioni di $O,\Omega$ e $o,\omega$. La disuguaglianza: $T(n) le disuguglianze dipendono un po' dai libri, ma l'espressione che ritengo più corretta è questa forma:
$ EE c>0,n_0>=0 : AA n>=n_0 0<=T(n)<=cf(n) $ e contrario Omega.

Considero quindi $ T(n) = 1/2 n^2 + 1/3 n^3 $ che corrisponde a $ T(n)= O(n^2)+O(n^3) $ la quale per la $iii$ è $ O(max(n^2,n^3))=O(n^3)$; infatti presi due valori $c=100 , n_0=100 $ faccio vedere che vale la $i$.
Scegliendo però $ c= 1/100, $ a prescindere dal valore di $n_0$ scelto, ottengo $ 1/100n^3<1/3n^3+1/2n^2 $ che da conferma alla $ ii $ Dove sbaglio?

Non mi piace molto come hai espresso il tutto. Vuoi dimostrare che $T(n) in O(n^3)$ non si applica la III (che è in parte corretto, ma nasconde ciò che accade)
$ 1/3 n^3 + 1/2 n^2 <= 1/3 n^3 + 1/2 n^3 = 5/6n^3 <= cn^3$ per $c>=5/6 \wedge n>=0$

lascio te correggere la dimostrazione per $\Omega$, la limitazione inferiore.

[Slashino1]

"hamming_burst":
Non mi piace molto come hai espresso il tutto. Vuoi dimostrare che $T(n) in O(n^3)$ non si applica la III (che è in parte corretto, ma nasconde ciò che accade)
$ 1/3 n^3 + 1/2 n^2 <= 1/3 n^3 + 1/2 n^3 = 5/6n^3 <= cn^3$ per $c>=5/6 \wedge n>=0$

lascio te correggere la dimostrazione per $\Omega$, la limitazione inferiore.

Così facendo, in pratica, hai dimostrato che se $T(n)=O(f_1(n))+O(f_2(n)) $ allora $ T(n) in O(max(f_1,f_2)) $ nel caso particolarizzato alle funzioni che ho scelto io, giusto?

Per quanto riguarda l'altra, ragionando in modo analogo:

$1/3n^3+1/2n^2>= 1/3n^2+1/2n^2 =5/6n^2$ quindi $1/3n^3+1/2n^2 >=cn^2 AA c<=5/6, AA x>=0 $ ovvero ( tornando alla definizione formale del limite inferiore )
$ EE c,n_0 : AA n>=n_0 0<=f(n)<=T(n) $. In definitiva $ 1/3n^3+1/2n^2=T(n) in \Omega(n^2) $.
Ma quindi, volendo generalizzare è vero dire
$T(n)=O(f_1(n))+O(f_2(n)) -> T(n) in O(max(f_1,f_2)) ^^ T(n) in \Omega(min(f_1(n),f_2(n)) $ ?