|
se <math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
=== Proprietà delle espressioni asintotiche ===
Per le espressioni asintotiche valgono le seguenti proprietà:
* <math> o(f) \subseteq O(f) </math>, cioè se <math>g = o(f) </math>, allora <math> g = O(f) </math>
* <math>f = O(g) </math> [[se e solo se]] <math>g = \Omega(f)</math>
* <math>f = o(g) </math> [[se e solo se]] <math>g = \omega(f)</math>
* <math>f = o(g)</math> implica <math>f = O(g) </math>, invece <math>f = O(g)</math> non implica <math>f = o(g)</math>,
* <math>O(f) + O(g) = O(\max \lbrace |f|,|g| \rbrace) </math>
* <math>O(k g) = O(g), k \ne 0</math>
* <math> O(f) + O(f) = O(f) </math>, cioè se <math> g=O(f) </math> e <math> h=O(f) </math>, allora <math> g+h = O(f) </math>
* <math> O(f) + o(f) = O(f) </math>, <math> o(f) + o(f) = o(f) </math>.
* <math> O(f) O(g) = O(f g) </math>, cioè se <math> h=O(f) </math> e <math> k=O(g) </math>, allora <math> h k = O(f g) </math>
* <math> O(f) o(g) = o(f g) </math> e dunque anche <math> o(f) o(g) = o(f g) </math>.
* <math> f = O(f) </math> (mentre <math>f = o(f) </math> implica che ''f'' è la funzione nulla)
Oltre a queste, all'interno di ognuna delle notazioni vale la [[proprietà transitiva]], cioè, ad esempio, se <math> f = O(g) </math> e <math>g = O(h) </math> allora <math>f = O(h) </math>.
La [[riflessività]] e la transitività di O implicano che esso è un [[preordine]], la cui [[relazione di equivalenza]] associata è proprio <math>\Theta </math>. Infatti dalla definizione di <math>\Theta </math>, è proprio <math> f = \Theta(g)\iff f=O(g)\land g=O(f) </math>.
Inoltre, se p è una costante, è definitivamente ''f(x) ≤ p'' se e solo se <math>f(n) = O(1)</math> e analogamente è definitivamente ''f ≥ p'' se e solo se <math>f(n) = \Omega(1)</math>.
===Problemi di notazione===
| 