Secondo questa notazione, è un insieme di funzioni che rappresenta l’ordine di grandezza asintotico inferiore (“più piccolo”) rispetto a quello del tempo impiegato dal processo , cioè cresce più velocemente di .
Esempio:
1 minuti
Secondo questa notazione, Ω(g(n)) è un insieme di funzioni che rappresenta l’ordine di grandezza asintotico inferiore (“più piccolo”) rispetto a quello del tempo impiegato dal processo f(n), cioè f(n) cresce più velocemente di g(n).
limn→∞g(n)f(n)=+∞→f(n)∈Ω(g(n))
Esempio: limn→∞lognn=+∞→n∈Ω(log(n))