Stima asintotica: differenze tra le versioni

Versione delle 19:51, 28 feb 2019

Versione delle 21:33, 28 feb 2019

Riga 321:

Oltre a queste, all'interno di ognuna delle notazioni vale la [[proprietà transitiva]], cioè, ad esempio, se <math> f = \mathrm{O}(g) </math> e <math> g = \mathrm{O}(h) </math> allora <math> f = \mathrm{O}(h) </math>.

La [[riflessività]] e la transitivitatransitività di <math> \mathrm{O} </math> 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=\mathrm{O}(g)\land g=\mathrm{O}(f) </math>.

Inoltre, se <math> p </math> è una costante, è definitivamente <math> f(x) \leq p </math> se e solo se <math> f(n) = \mathrm{O}(1) </math> e analogamente è definitivamente <math> f \geq p </math> se e solo se <math> f(n) = \Omega(1) </math>.