|
==Ordini di infinito ==
Una funzione <math>f(x)</math> si dice ''infinita'' in <math>x_0</math> se il suo [[Limite (matematica)|limite]] è infinito al tendere di <math>x</math> a <math>x_0</math>. In simboli, se
:<math> \lim_{x \to x_0}|f(x)| = +\infty </math>.
Per esempio <math>\frac{1}{x}</math> è infinita in <math>0</math> e <math>-e^{-x}</math> è infinita in <math>-\infty</math>.
Una successione (che può considerarsi una funzione definita nei numeri naturali) si dice ''infinita'' se il suo [[Limite (matematica)|limite]] è infinito al tendere di <math>n</math> all'infinito. In simboli: se
<math> \{a_n\} </math> è una successione di numeri reali,
<math> \lim_{n \to \infty}|a_n| = +\infty </math>.
Non tutti gli infiniti sono però identici tra loro: esiste infatti un ordine all'interno degli infiniti, che dipende dal tipo di andamento della [[Funzione (matematica)|funzione]] a infinito. Ecco alcuni tipi di infinito posti in ordine crescente: <math> a </math>, <math> b </math> e <math> c </math> sono numeri qualunque maggiori di 1, mentre <math> n </math> è l'indice della successione.
:<math> \log_alim_{n} \le n^bto \leinfty}|a_n| c^n= +\le n! \le n^n infty.</math>
Non tutti gli infiniti sono però identici tra loro: esiste infatti un ordine all'interno degli infiniti, che dipende dal tipo di andamento della [[Funzione (matematica)|funzione]] a infinito. Ecco alcuni tipi di infinito posti in ordine crescente: <math>a</math>, <math>b</math> e <math>c</math> sono numeri qualunque maggiori di 1, mentre <math>n</math> è l'indice della successione.
'''Nota''': il segno di <math> \,\le\, </math> va inteso nel senso dell'[[#O piccolo|o piccolo]].
:<math>\log_a{n} \le n^b \le c^n \le n! \le n^n.</math>
===Altri esempi===
'''Nota''': il segno di <math>\le</math> va inteso nel senso dell'[[#O piccolo|o piccolo]].
Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove <math> \mathop{\mathrm{Ord}}_z </math> indica l'ordine per la variabile tendente a <math> z </math>'':
===Altri esempi===
<math> \mathrm{Ord}_{+\infty} \, x^a \le \mathrm{Ord}_{+\infty} \, e^x </math>
Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove <math>\mathop{\mathrm{Ord}}_z</math> indica l'ordine per la variabile tendente a <math>z</math>:
:<math> \mathrm{Ord}_0_{+\infty} \, \frac{1}{\sqrt x}^a \le \mathrm{Ord}_0_{+\infty} \, \frac{1} {e^x} </math>
:<math> \mathrm{Ord}_1_0 \, \frac{1} {\sqrt x -1} \le \mathrm{Ord}_1_0 \, \frac{1} { x -1} </math>
:<math>\mathrm{Ord}_1 \, \frac{1} {\sqrt x -1} \le \mathrm{Ord}_1 \, \frac{1}{ x -1}.</math>
==Ordini di infinitesimo ==
Una funzione <math>f</math> si dice ''infinitesima'' in <math>x_0</math> se il suo [[Limite (matematica)|limite]] è <math>0</math> al tendere di <math>x</math> a <math>x_0</math>. In simboli, se
<math> \lim_{x \to x_0}f(x) = 0 </math>.
:<math>\lim_{x \to x_0}f(x) = 0.</math>
Per esempio <math>\frac{1}{x}</math> ed <math>e^{-x}</math> sono infinitesime in <math>+\infty</math> (la prima anche in <math>-\infty</math>).
Una successione <math> \{a_n\}</math> si dice ''infinitesima'' quando il suo [[Limite (matematica)|limite]] è uguale a zero al tendere di <math>n</math> all'infinito:
:<math> \lim_{n \to \infty} a_n = 0 .</math>.
Come per gli infiniti esistono successioni che tendono a zero più velocemente di altre; prendendo i [[elemento inverso|reciproci]] della sequenza di diseguaglianze sopra e cambiando i <math> \le </math> in <math> \ge </math> si ha la tabella corrispondente
:<math> \tfrac{1}{n^n} \le \tfrac{1}{n!} \le \tfrac{1}{c^n} \le \tfrac{1}{n^b} \le \tfrac{1}{\log_a n} .</math>
'''Nota''': l'''[[#O piccolo|ordine]]'' di infinitesimo di <math> \tfrac{1}{n^n} </math> è ''maggiore'' di quello di <math> \tfrac{1}{n!} </math>, visto che quest'ultimo tende a zero più ''lentamente''.
=== Altri tipi di limiti ===
Ecco alcuni esempi di ordini di infinitesimo riferiti a funzioni:
:<math> \mathrm{ord}_0 \, \sqrt{x} \le \mathrm{ord}_0 \, x \le \mathrm{ord}_0 \, x^2 \le \mathrm{ord}_0 \, x^3 ;</math>
:<math> \mathrm{ord}_{-\infty} \, \frac{1}{x^n} \le \mathrm{ord}_{-\infty} \, e^x .</math>
==Successioni asintotiche ==
Date due successioni <math> a_n </math> e <math> b_n </math>, esse si dicono ''asintotiche'' o ''asintoticamente equivalenti'' e lo si indica con la notazione <math> a_n \sim b_n </math> se<br />
<math> \lim_{n \to \infty} \frac{a_n} {b_n} = 1 </math><br />
:<math>\lim_{n \to \infty} \frac{a_n}{b_n} = 1.</math>
(Ovviamente si deve supporre che esista un <math> N</math> tale che <math> b_n \not=ne 0, \ \quad \forall n \ge N </math>).
In questo caso è possibile creare delle catene di relazioni asintotiche:
:<math> \mathrmtext{se }\, \ a_n \sim b_n \sim ... \ldots\sim c_n, \ \,\mathrmtext{ allora }\, \ a_n \sim c_n .</math>
Un'espressione composta da prodotto o quoziente di più fattori può essere stimata fattore per fattore:
:<math> \mathrmtext{se }\, \ a_n \sim a'_n, \ b_n \sim b'_n, \ c_n \sim c'_n , \text{ \,\mathrm{allora }\, \ \frac{a_n b_n} {c_n} \sim \frac{a'_n b'_n} {c'_n} .</math>
La relazione <math> \sim </math> è una [[relazione di equivalenza]], in quanto valgono le [[proprietà riflessiva]], [[proprietà simmetrica|simmetrica]] e [[proprietà transitiva|transitiva]] rispetto all'operatore.
==Regole operative==
===Confronti fra infiniti e infinitesimi ===
Siano <math> a_n </math> e <math> b_n </math> due successioni infinite. Per il [[Limite (matematica)|limite]] del rapporto abbiamo che se <math> \lim_{n\to +\infty} \frac{a_n} {b_n} </math> è uguale a:
{|
|
* <math> 0 </math>:
| <math> a_n </math> è un infinito di ordine inferiore a <math> b_n </math>
|-
|
* <math>l \not=ne 0 </math>:
| <math> a_n </math> e <math> b_n </math> sono infiniti dello stesso ordine
|-
|
* <math> \pm \infty </math>:
| <math> a_n </math> è un infinito di ordine superiore a <math> b_n </math>
|-
|
* non esiste:
| <math> a_n </math> e <math> b_n </math> non sono confrontabili.
|}
Valgono anche le implicazioni inverse: se <math> a_n </math> domina <math> b_n </math> allora il limite è infinito, e così via.
Lo stesso ragionamento può essere ripetuto per gli infinitesimi. Siano <math> a_n </math> e <math> b_n </math> due successioni infinitesime. Per il [[Limite (matematica)|limite]] del rapporto abbiamo che se <math> \lim_{n\to +\infty} \frac{a_n} {b_n} </math> è uguale a:
{|
|
* <math> 0 </math>:
|<math> a_n </math> è un infinitesimo di ordine superiore a <math> b_n </math>
|-
|
* <math> l \not=ne 0 </math>:
|<math> a_n </math> e <math> b_n </math> sono infinitesimi dello stesso ordine
|-
|
* <math>\pm \infty </math>:
|<math> a_n </math> è un infinitesimo di ordine inferiore a <math> b_n </math>
|-
|
* non esiste:
| <math> a_n </math> e <math> b_n </math> non sono confrontabili.
|}
===Principio di sostituzione degli infiniti ===
Siano <math> a_n </math> e <math> b_n </math> due infiniti. Nel calcolo del [[Limite (matematica)|limite]] del rapporto si possono aggiungere o togliere al numeratore e al denominatore degli infiniti che siano di ordine inferiore, in base a quanto visto nel paragrafo precedente.
Infatti, ad esempio:
:<math> \lim_{n \to +\infty} \frac{n^2 + \sqrt n} {5 n 5n^ 2 - 3 n3n} = \lim_{n \to +\infty} \frac{n^2} {5 n 5n^ 2 - 3 n3n} + \lim_{n \to +\infty} \frac{\sqrt n} {5 n5n^ 2 -3 n 3n} = \lim_{n \to +\infty} \frac{n^2} {5 n 5n^ 2 } + 0 = \frac{1} {5} .</math>
===Principio di sostituzione degli infinitesimi ===
Siano <math> a_n </math>, <math> b_n </math> due successioni infinitesime. Nel calcolo del [[Limite (matematica)|limite]] del rapporto si possono aggiungere o togliere, in una somma di infinitesimi, al numeratore e al denominatore degli infinitesimi che siano di ordine superiore, in base a quanto visto nel paragrafo precedente.
Si ottiene così la seguente equazione utile per la risoluzione di problemi di limiti indeterminati:
:<math> \lim_{n \to \infty} \frac{a_n} {b_n} = \lim_{n \to \infty} \frac{a_n + a'_n} {b_n + b'_n} .</math>
Ad esempio:
:<math> \lim_{n \to \infty} \frac{n^{-2} + n ^ {-\frac{1}{2}} } {5n^{-3} - 4n^{-1} } = \lim_{ n \to \infty} \frac{ n ^ {-\frac{1}{2}} } { -4n ^ { -1 } } = - \infty .</math>
===Principio di sostituzione degli infinitesimi equivalenti===
Siano <math> f(x) </math>, <math> g(x) </math> due funzioni infinitesime. Per il limite del rapporto <math> \frac{f(x)} {g(x)} </math> vale
:<math> \lim_{x \to x_0} \frac{f(x)} {g(x)} = \lim_{x \to x_0} \frac{h(x)} {k(x)} </math>
se risulta <math> f(x) \sim h(x) </math> e <math>g(x) \sim k(x) </math>, cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.
:<math> \lim_{x \to x_0} \frac{f(x)}{g(x)} = \lim_{x \to x_0} \frac{h(x)}{k(x)} </math>
Ad esempio, essendo <math> \tan x \sim x</math>:
:<math>\lim_{x \to 0} \frac{\tan x} {\sqrt x} = \lim_{x \to 0}\frac{x} {\sqrt x} = 0 </math>
se risulta <math>f(x) \sim h(x)</math> e <math>g(x) \sim k(x)</math>, cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.
Ad esempio, essendo <math>\tan x \sim x</math>:
:<math>\lim_{x \to 0} \frac{\tan x}{\sqrt x} = \lim_{x \to 0}\frac{x}{\sqrt x} = 0.</math>
== Espressioni asintotiche ==
Nella valutazione del comportamento asintotico di un [[algoritmo]] vengono introdotte delle relazioni tra successioni numeriche che sono divenute di uso corrente. Tali notazioni si possono anche utilizzare per funzioni reali, con la specifica del valore del dominio a cui tende la variabile, che può non essere <math> \infty </math>.
===Schema generale===
Le definizioni che introdurremo qui di seguito sono molteplici e a prima vista possono sembrare disorientanti, oppure può risultare faticoso ricordarle tutte assieme e confrontarle fra di loro. Per questa ragione, cioè per fornire un quadro d'insieme che sia anche di aiuto mnemonico, prima di procedere alle definizioni rigorose e specifiche illustreremo in modo discorsivo lo schema generale su cui si basano tutti questi concetti.
Quasi tutte le definizioni che stiamo per introdurre hanno lela seguente struttura:
Diciamo che la successione <math>f(n)</math> è una <math>\mathrm{X}</math> della successione <math>g(n)</math>, e scriviamo
:<math>f(n) = \mathrm{X}(g(n))</math>
se e solo se
:<math>[\mathrm{quantificatore}]C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \prec \succ C |g(n)|.</math>
Diciamo che la successione <math> f(n) </math> è una <math> \mathrm{X} </math> della successione <math> g(n) </math>, e scriviamo
:<math> f(n) = \mathrm{X}(g(n)) </math>
se e solo se:
:<math> [\mathrm{quantificatore}]C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \prec \succ C |g(n)| </math>
Nelle parentesi quadre abbiamo specificato le parti della definizione che di volta in volta variano. Al posto di ''[quantificatore]'' ci possono andare i due [[quantificatori]] <math> \forall </math> ed <math> \exists </math>, mentre la <math>\prec \succ</math> è una relazione d'ordine, e può essere <math> \le</math> o <math>\ge </math>. Abbiamo pertanto due parametri ognuno dei quali può assumere due valori diversi, sicché le definizioni possibili saranno quattro:
{| class="wikitable" cellpadding="15"
! !!<math> \forall </math> !! <math>\exists</math>
|}
Per distinguere questi quattro casi bisogna che anche il simbolo <math> \mathrm{X}(\cdot) </math> che definisce la relazione fra <math> f(n) </math> e <math> g(n) </math> possa assumere quattro valori diversi, definiti in qualche modo da due parametri: uno che definisce il quantificatore e l'altro che definisce la relazione d'ordine.
Tali simboli sono i seguenti:
*<math> \mathrm{O} </math> ("O grande") / <math> \mathrm{o} </math> ("o piccolo"),;
*<math> \Omega </math> ("omega grande") / <math>\omega </math> ("omega piccolo").
Come si vede si tratta effettivamente di quattro simboli definiti da due parametri:
*italianolatino/greco;
*piccolo/grande.
Di questi due parametri il primo, cioè "italianolatino/greco", viene utilizzato per specificare la relazione d'ordine, secondo la seguente associazione:
*italianolatino: <math> \le </math>;
*greco: <math> \ge </math>.
mentreMentre il secondo, cioè "piccolo/grande", viene utilizzato per specificare il quantificatore, secondo la seguente associazione:
*piccolo: <math> \forall </math>;
*grande: <math> \exists </math>.
Queste associazioni possono sembrare decisamente controintuive. Ad esempio sembrerebbe più utile associare "piccolo/grande" alle relazioni d'ordine, in modo tale che "piccolo" stia per "più piccolo" (cioè <math> \le </math>) e "grande" stia per "più grande (cioè <math> \ge </math>). Invece per rendere la relazione d'ordine si usa lo strano parametro che abbiamo definito "italianolatino/greco".
Tutte queste apparenti stranezze si risolvono immediatamente non appena si faccia un po' di opera "filologica". In particolare è importante tenere presente che originariamente quella che ora chiamiamo "o" era in realtà una "omicron", cioè un'altra lettera greca ([[O-grande]]). Infatti nell'alfabeto greco esistono due lettere corrispondenti alla nostra "o":
* la "o-micron", che significa "o piccola";
* la "o-mega", che significa "o grande".
Pertanto originariamente la notazione indicava proprio quello che abbiamo intenzione di indicare noi: la "o piccola" ("omicron") stava per <math> \le </math> e la "o grande" ("omega") stava per <math> \ge </math>.
Quanto al parametro che fino a qui abbiamo indicato con "grande/piccolo", sappiamo bene che questo è solo un modo colloquiale di riferirsi alle lettere "maiuscole/minuscole".
Dunque, se torniamo all'uso originale di tutti questi simboli, abbiamo le seguenti associazioni:
*"micron" ("piccolo"): <math> \le </math>
*"mega" ("grande"): <math> \ge </math>
*"minuscolo": <math> \forall </math>
*"maiuscolo": <math> \exists </math>
{| class="wikitable" cellpadding="15"
|-
! <math>\le</math>
|| <math> \mathrm{o} </math>
|| <math> \mathrm{O} </math>
|-
! <math>\ge</math>
|| <math> \omega </math>
|| <math> \Omega </math>
|}
Forti di questo schema generale, che può esserci utile anche come regola mnemonica, proviamo a scrivere, ad esempio, la definizione della seguente espressione:
:<math> f(n) = \mathrm{O}(g(n)) </math>
:<math>f(n) = \mathrm{O}(g(n)).</math>
Dobbiamo dire che la <math> f(n) </math> è una "o-micron maiuscola" della <math> g(n) </math>. Ricordiamo che:
*"micron" sta per "più piccolo", cioè <math> \le </math>;
*"maiuscolo" sta per: <math> \exists </math> (almeno un) <math> C </math> tale che...
Ecco dunque la definizione cercata:
Diciamo che <math> f(n) = \mathrm{O}(g(n)) </math> se e solo se:
:<math> \exists C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \le C |g(n)| </math>
:<math>\exists C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \le C |g(n)|.</math>
Infine ci interessa conoscere le implicazioni fra tutte queste relazioni. Tali implicazioni si possono ricavare immediatamente dalle seguenti considerazioni:
1) Ricordando che, in generale:
:<math> a \le b \ \Leftrightarrow \ b \ge a </math>
allora <math> f </math> è una "omicron" (cioè "più piccola") di <math> g </math> se e solo se <math>g</math> è una "omega" (cioè "più grande") di <math>f</math>:
:<math>f(x) = \mathrm{O} / \mathrm{o}(g(x)) \ \Leftrightarrow \ g(x) = \Omega / \omega (f(x)) </math>
:<math>a \le b \ \Leftrightarrow \ b \ge a,</math>
2) Se una relazione è vera <math> \forall C </math> allora in particolare <math> \exists </math> un certo <math> C </math> che la soddisfa. Dunque se una successione <math>f(n)</math> è una "minuscola" della successione <math> g(n) </math> allora è anche "maiuscola" di essa:
:<math>f(x) = \mathrm{o}/\omega(g(x)) \ \Rightarrow \ f(x) = \mathrm{O} / \Omega (g(x)) </math>
allora <math>f</math> è una "omicron" (cioè "più piccola") di <math>g</math> se e solo se <math>g</math> è una "omega" (cioè "più grande") di <math>f</math>:
:<math>f(x) = \mathrm{O} / \mathrm{o}(g(x)) \ \Leftrightarrow \ g(x) = \Omega / \omega (f(x)).</math>
2) Se una relazione è vera <math>\forall C</math> allora in particolare <math>\exists</math> un certo <math>C</math> che la soddisfa. Dunque se una successione <math>f(n)</math> è una "minuscola" della successione <math>g(n),</math> allora è anche "maiuscola" di essa:
:<math>f(x) = \mathrm{o}/\omega(g(x)) \ \Rightarrow \ f(x) = \mathrm{O} / \Omega (g(x)).</math>
Ciò può essere espresso anche dicendo che l'insieme delle "minuscole" di una certa funzione è contenuto nell'insieme delle "maiuscole" di quella funzione, e questa vale anche come regola mnemonica per il parametro "maiuscolo/minuscolo".
=== O grande ===
{{vedi anche|O-grande}}
Siano <math>f</math> e <math>g</math> due funzioni definite su <math>\N</math> a valori in <math>\R</math>.
SianoSi dice che <math> f (n)</math> eè <math>un g'''o grande''' di </math> dueg(n) funzioni definite su <math>\N</math> a valori, in <math>\R</math>.simboli:
Si dice che <math> f(n) </math> è un '''o grande''' di <math> g(n) </math>, in simboli
:<math> f(n) = \mathrm{O}(g(n)) </math>
se <math> \exists c > 0, n_0 \in N \colon \ \ \ \ \forall n \ge n_0, \ \ |f(n)| \le c |g(n)| .</math>.
Si dice anche che <math> f(n) </math> ha ordine di grandezza minore o uguale a quello di <math> g(n) </math>, cioè la funzione <math> g(n) </math> domina <math> f(n) </math>.
Se la successione <math> g(n) </math> ha valori definitivamente diversi da zero, una condizione equivalente, sfruttando il [[limite superiore e limite inferiore|limite superiore]], è che sia <math> \limsup_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| < \infty</math>.
==== Esempi ====
:<math> n = \mathrm{O}\left( 2n) \right);</math>
:<math> n = \mathrm{O}\left( \frac{n} {2} \right) ;</math>
:<math> 4n^2 + n = \mathrm{O}(n^2);</math>
:<math> n \log n \neq \mathrm{O}(n).</math>
===O piccolo===
Si dice che <math>f(n)</math> è un '''o-piccolo''' di <math>g(n)</math>, in simboli
Si dice che :<math> f(n) </math> è un= '''\mathrm{o-piccolo''' di <math> }(g(n) )</math>, in simboli
se <math> f(\lim_{n) =\to \mathrm{oinfty} \frac{f(n)}{g(n))} = 0.</math>
se <math> \lim_{n \to \infty} \frac{f(n)} {g(n)} = 0 </math>
=== Omega grande ===
Si dice che <math>f(n)</math> è un '''omega grande''' di <math>g(n)</math>, in simboli
Si dice che :<math> f(n) </math> è un '''omega grande''' di <math>= \Omega(g(n) )</math>, in simboli
se <math>\exists c >0, n_0 \in \N\colon \ \ \ \ \forall n \ge n_0, \ \ |f(n) =| \Omega(geq c |g(n)) |.</math>
seSi dice anche che <math>f(n)</math> \existsha cordine >0,di n_0grandezza \inmaggiore \N\colono \uguale \a \quello \di \forall <math>g(n)</math>, \geo n_0,che \ \<math> |fg(n)| \geq</math> cè |gdominata da <math>f(n)|</math>.
Si dice anche che <math> f(n) </math> ha ordine di grandezza maggiore o uguale a quello di <math> g(n) </math>, o che <math> g(n) </math> è dominata da <math> f(n) </math>.
Usando la notazione del [[limite superiore e limite inferiore|limite inferiore]], una condizione equivalente è che sia
<math> \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math>
:<math> \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0.</math>
===Omega piccolo ===
Si dice che <math>f(n)</math> è un '''omega piccolo''' di <math>g(n)</math>, in simboli
Si dice che :<math> f(n) </math> è un= '''\omega piccolo''' di <math> (g(n) )</math>, in simboli
se <math> f(\lim_{n) =\to \omegainfty} \frac{f(n)}{g(n))} = \infty.</math>
se <math> \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty </math>
=== Theta ===
Le funzioni <math>f(n)</math> e <math>g(n)</math> sono dette avere lo stesso ordine di grandezza, in simboli
:<math> f(n) </math> e <math>= \Theta(g(n) )</math> sono dette avere lo stesso ordine di grandezza, in simboli
se <math>\exists c_1,c_2 > 0, n_0 \in \N \colon \ \ \ \ \forall n \ge n_0, \ \ c_1 |g(n)| \leq |f(n)| \le c_2 |g(n)|</math>.
<math> f(n) = \Theta(g(n)) </math>
seUsando <math>i \existslimiti c_1superiore e inferiore,c_2 questa condizione si può enunciare come <math> 0, n_0< \inliminf_{n \Nto \coloninfty} \left| \frac{f(n)} \{g(n)} \right| \forallle \limsup_{n \ge n_0,to \infty} \ c_1 |g(n)left| \leq |frac{f(n)|} \leq c_2 |{g(n)} \right| < \infty.</math>.
Usando i limiti superiore e inferiore, questa condizione si può enunciare come <math> 0 < \liminf_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| \leq \limsup_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| < \infty </math>
-->
=== Proprietà delle espressioni asintotiche ===
Per le espressioni asintotiche valgono le seguenti proprietà:
===== Proprietà di base =====
# <math> f = \mathrm{O}(g) \iff g = \Omega(f) </math>.
# <math> f = \mathrm{o}(g) \iff g = \omega(f) </math>.
# <math> f = \mathrm{O}(f) </math> .
# <math> f = \mathrm{o}(f) \ \Rightarrow \ f \equiv 0 </math>.
===== Implicazioni =====
# <math> g = \mathrm{o}(f) \ \Rightarrow \ g = \mathrm{O}(f) </math>.
#:cioè: <math> o(f) \subseteq \mathrm{O}(f) </math>.
# <math> f = \mathrm{O}(g) \ \not \Rightarrow \ f = \mathrm{o}(g) </math>.
===== Somme di funzioni =====
# <math> \mathrm{O}(f) + \mathrm{O}(g) = \mathrm{O}(\max \lbrace |f|,|g| \rbrace) </math>.
# <math> \mathrm{O}(k g) = \mathrm{O}(g), \ \forall k \in \R_0 </math>.
# <math> \mathrm{O}(f) + \mathrm{O}(f) = \mathrm{O}(f) </math>.
#:cioè <math> g=\mathrm{O}(f) \land h=\mathrm{O}(f) \ \Rightarrow g+h = \mathrm{O}(f) </math>.
# <math> \mathrm{O}(f) + \mathrm{o}(f) = \mathrm{O}(f) </math>.
# <math> \mathrm{o}(f) + \mathrm{o}(f) = \mathrm{o}(f) </math>.
===== Prodotti =====
# <math> \mathrm{O}(f) \mathrm{O}(g) = \mathrm{O}(f g) </math>
#:cioè <math> h=\mathrm{O}(f) \land k=\mathrm{O}(g) \ \Rightarrow h k = \mathrm{O}(f g) </math>.
# <math> \mathrm{O}(f) \mathrm{o}(g) = \mathrm{o}(f g) </math>.
# <math> \mathrm{o}(f) \mathrm{o}(g) = \mathrm{o}(f g) </math>.
==== Prodotti ====
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>.
# <math>\mathrm{O}(f) \mathrm{O}(g) = \mathrm{O}(f g)</math>
#:cioè <math>h=\mathrm{O}(f) \land k=\mathrm{O}(g) \ \Rightarrow h k = \mathrm{O}(f g)</math>.
# <math>\mathrm{O}(f) \mathrm{o}(g) = \mathrm{o}(f g)</math>.
# <math>\mathrm{o}(f) \mathrm{o}(g) = \mathrm{o}(f g)</math>.
LaOltre [[riflessività]]a equeste, la transitivitaall'interno di <math>ognuna \mathrm{O}delle </math>notazioni implicano che esso è un [[preordine]],vale la cui [[relazioneproprietà di equivalenzatransitiva]], associatacioè, èad proprioesempio, <math>\Thetase </math>.f Infatti= dalla definizione di <math>\Theta mathrm{O}(g)</math>, è proprioe <math> fg = \Theta(g)\iff f=\mathrm{O}(gh)\land</math> allora <math>f g= \mathrm{O}(fh) </math>.
Inoltre,La se[[riflessività]] e la transitività di <math> p \mathrm{O}</math> èimplicano unache costante,esso è definitivamenteun <math>[[preordine]], f(x)la \leqcui p[[relazione </math>di seequivalenza]] eassociata soloè seproprio <math> f(n) = \mathrm{O}(1) Theta</math>. eInfatti analogamentedalla èdefinizione definitivamentedi <math> f \geq p Theta</math>, seè e solo seproprio <math>f = \Theta(g)\iff f=\mathrm{O}(ng)\land g= \Omegamathrm{O}(1f) </math>.
Inoltre, se <math>p</math> è una costante, è definitivamente <math>f(x) \le p</math> se e solo se <math>f(n) = \mathrm{O}(1)</math> e analogamente è definitivamente <math>f \ge p</math> se e solo se <math>f(n) = \Omega(1)</math>.
===Problemi di notazione===
L'affermazione <math>f(x)</math> è un o grande di <math>g(x)</math> è di solito scritta come <math>f(x)=\mathrm{O}(g(x))</math>. Questo è un leggero abuso di notazione, in quanto non si sta asserendo l'uguaglianza delle due funzioni. Inoltre la proprietà non è simmetrica:
:<math>\mathrm{O}(x) = \mathrm{O}(x^2) \ \ \mathrm{ ma } \ \ \mathrm{O}(x^2)\ne \mathrm{O}(x).</math>
L'affermazione <math> f(x) </math> è un o grande di <math> g(x) </math> è di solito scritta come <math> f(x)=\mathrm{O}(g(x)) </math>. Questo è un leggero abuso di notazione, in quanto non si sta asserendo l'uguaglianza delle due funzioni. Inoltre la proprietà non è simmetrica:
Per questa ragione, alcuni autori preferiscono una notazione insiemistica e scrivono <math>f \in \mathrm{O}(g)</math>, pensando a <math>\mathrm{O}(g)</math> come alla classe di tutte le funzioni dominate da <math>g</math>, o usano una notazione introdotta da [[Godfrey Harold Hardy|Hardy]], che è la seguente:
:<math> \mathrm{O}(x) = \mathrm{O}(x^2) \ \ \mathrm{ ma } \ \ \mathrm{O}(x^2)\ne \mathrm{O}(x) </math>.
:<math>f\lesssim g \iff f \in \mathrm{O}(g)</math> e <math>f\ll g \iff f\in \mathrm{o}(g).</math>
Per questa ragione, alcuni autori preferiscono una notazione insiemistica e scrivono <math> f \in \mathrm{O}(g) </math>, pensando a <math>\mathrm{O}(g) </math>'' come alla classe di tutte le funzioni dominate da <math> g </math>, o usano una notazione introdotta da [[Godfrey Harold Hardy|Hardy]], che è la seguente:
:<math> f\lesssim g \iff f \in \mathrm{O}(g) </math> e <math> f\ll g \iff f\in \mathrm{o}(g) </math>.
=== Grafici ===
* [[Teoria della complessità computazionale]]
* [[Algoritmo]]
==Collegamenti esterni==
* {{Collegamenti esterni}}
{{analisi_matematica}}
{{Portale|matematica}}
| 