Limite superiore asintotico e la notazione O grande

Date due funzioni asintoticamente non negative $f(n)$ e $g(n)$ si di che $f(n)$ è in $g(n)$ se esistono due costanti $c>0$ e $n_0\ge 0$ tali che $f(n)\le cg(n)$ per ogni $n\ge n_0$ Quindi in $O(g(n))$ troviamo tutte le funzioni che risultano dominate dalla funzione $g(n)$.

Esempio: É facile vedere che $\sqrt{n}=O(n)$ in quanto la funzione radice cresce meno della funzione lineare. Per provarlo in modo formale possiamo utilizzare i limiti ricordando che $f(n)\in O(g(n))$ se ${\lim }_{x\to +\infty }\frac{f(n)}{g(n)}\ne +\infty$ Generalizzando il nostro caso otteniamo:

${\lim }_{x\to +\infty }\frac{n^{\frac{1}{a}}}{n^b}=0$ Oppure = 1 se $a=b=1$

Altri Esempi