notazione O-grande

Secondo questa notazione, $O(g(n))$ è un insieme di funzioni che rappresenta l’ordine di grandezza asintotico superiore (“più grande”) rispetto a quello di $f(n)$, cioè , cioè $f(n)$ cresce più lentamente di $g(n)$. ${\lim }_{n\to +\infty }\frac{f(n)}{g(x)}=0\to f(x)\in O(g(x))$

Esempio di confronto asintotico tra $\log n$ e $n$: ${\lim }_{n\to \infty }\frac{\log n}{n}=0\to log(n)\in O(n)$ Esempio di confronto asintotico tra $n$ e $\sqrt{n}$ ${\lim }_{n\to \infty }\frac{\sqrt{n}}{n}={\lim }_{n\to \infty }\frac{1}{\sqrt{n}}=0\to \sqrt{n}\in O(n)$

---

Se consideriamo un’algoritmo dove $t(x)$ è il suo tempo di esecuzione e $x$ è la quantità di dati che l’algoritmo processa, la notazione $O(t(x))$ da l’ordine di grandezza asintotico a quello del tempo impiegato dal processo.