Limite inferiore asintotico e la notazione Ω

Date due funzioni asintoticamente positive $f(n)$ e $g(n)$ si dice che $f(n)$ è in $\Omega (g(n))$ se esistono due costanti $c>0$ e $n_0\ge 0$ tali che $f(n)\ge cg(n)$ per ogni $n\ge n_0$ In $\Omega (g(n))$ troviamo tutte le funzioni che dominano la funzione $g(n)$. Esempio: Provare che

$\frac{n}{{\log }_{e}n}\in \Omega (\sqrt{n}{\log }_{e}n)$

Per provarlo possiamo utilizzare il metodo del rapporto dei limiti ricordando che $f(n)\in \Omega (g(n))$ se il $lim\to +\infty$ del rapporto fra $f(n)$ e $g(n)$ $\ne 0$. Nel nostro caso otteniamo:

${\lim }_{n\to +\infty }\frac{\sqrt{n}}{{\log }^{2}n}=+\infty$

Ricordando che la radice cresce più velocemente del logaritmo

Altri Esempi