Originariamente inviato da GIULIOS
posso considerarla anche Θ( radice quarta di n ) ?
Direi proprio di no. Per valere quella relazione la funzione radice cubica dovrebbe essere, oltre che OMEGA(radice quarta), anche O(radice quarta), cosa (quest'ultima) sicuramente non vera perché non vedo come possa esistere un valore di c > 0 tale che, da un certo n0 in poi, risulti sempre n^1/3 <= c*n^1/4. Insomma la funzione radice quarta da un certo punto in poi cresce sicuramente meno rapidamente della radice terza, anche se scalata per una qualsiasi costante positiva c.
E a proposito della big-O notation, credo che in quel caso valga anche la little-O.