Quando due successioni sono entrambe infinitesime o entrambe infinite è utile poter stabilire un confronto tra di esse per poter capire quale delle due tenda più rapidamente a 0 o all'infinito.
In questo articolo si fa riferimento allo studio di stime asintotiche per le successioni. Operazioni analoghe si possono fare per le funzioni reali di una variabile reale, dove al posto di infinito può trovarsi qualunque punto di accumulazione comune alle due funzioni.
Una funzione
si dice infinita in
se il suo limite è infinito al tendere di
a
. In simboli, se

Per esempio
è infinita in
e
è infinita in
.
Una successione (che può considerarsi una funzione definita nei numeri naturali) si dice infinita se il suo limite è infinito al tendere di
all'infinito. In simboli: se
è una successione di numeri reali,
.
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 a infinito. Ecco alcuni tipi di infinito posti in ordine crescente:
,
e
sono numeri qualunque maggiori di 1, mentre
è l'indice della successione.
Nota: il segno di
va inteso nel senso dell'o piccolo.
Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove
indica l'ordine per la variabile tendente a
:
Una funzione
si dice infinitesima in
se il suo limite è
al tendere di
a
. In simboli, se
.
Per esempio
ed
sono infinitesime in
(la prima anche in
).
Una successione
si dice infinitesima quando il suo limite è uguale a zero al tendere di
all'infinito:
.
Come per gli infiniti esistono successioni che tendono a zero più velocemente di altre; prendendo i reciproci della sequenza di diseguaglianze sopra e cambiando i
in
si ha la tabella corrispondente
Nota: l'ordine di infinitesimo di
è maggiore di quello di
, visto che quest'ultimo tende a zero più lentamente.
Ecco alcuni esempi di ordini di infinitesimo riferiti a funzioni:
Date due successioni
e
, esse si dicono asintotiche o asintoticamente equivalenti e lo si indica con la notazione
se

(Ovviamente si deve supporre che esista un
tale che
).
In questo caso è possibile creare delle catene di relazioni asintotiche:
Un'espressione composta da prodotto o quoziente di più fattori può essere stimata fattore per fattore:
La relazione
è una relazione di equivalenza, in quanto valgono le proprietà riflessiva, simmetrica e transitiva rispetto all'operatore.
Siano
e
due successioni infinite. Per il limite del rapporto abbiamo che se
è uguale a:
:
|
è un infinito di ordine inferiore a
|
:
|
e sono infiniti dello stesso ordine
|
:
|
è un infinito di ordine superiore a
|
|
e non sono confrontabili.
|
Valgono anche le implicazioni inverse: se
domina
allora il limite è infinito, e così via.
Lo stesso ragionamento può essere ripetuto per gli infinitesimi. Siano
e
due successioni infinitesime. Per il limite del rapporto abbiamo che se
è uguale a:
:
|
è un infinitesimo di ordine superiore a
|
:
|
e sono infinitesimi dello stesso ordine
|
:
|
è un infinitesimo di ordine inferiore a
|
|
e non sono confrontabili.
|
Siano
e
due infiniti. Nel calcolo del 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:
Siano
,
due successioni infinitesime. Nel calcolo del 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:
Ad esempio:
Principio di sostituzione degli infinitesimi equivalenti[modifica | modifica wikitesto]
Siano
,
due funzioni infinitesime. Per il limite del rapporto
vale

se risulta
e
, cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.
Ad esempio, essendo
:

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
.
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 le seguente struttura:
Diciamo che la successione
è una
della successione
, e scriviamo

se e solo se:
![[{\mathrm {quantificatore}}]C\ \exists N\colon \ \ \ \ \forall n>N,\ \ |f(n)|\prec \succ C|g(n)|](https://wikimedia.org/api/rest_v1/media/math/render/svg/74bfde86c97f517a768a49d91de477e6d713c0a5)
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
ed
, mentre la
è una relazione d'ordine, e può essere
o
. Abbiamo pertanto due parametri ognuno dei quali può assumere due valori diversi, sicché le definizioni possibili saranno quattro:
|
 |
|
|
|
|
|
|
|
Per distinguere questi quattro casi bisogna che anche il simbolo
che definisce la relazione fra
e
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:
("O grande") /
("o piccolo"),
("omega grande") /
("omega piccolo").
Come si vede si tratta effettivamente di quattro simboli definiti da due parametri:
- latino/greco
- piccolo/grande
Di questi due parametri il primo, cioè "latino/greco", viene utilizzato per specificare la relazione d'ordine, secondo la seguente associazione:
- latino:

- greco:

mentre il secondo, cioè "piccolo/grande", viene utilizzato per specificare il quantificatore, secondo la seguente associazione:
- piccolo:

- grande:

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è
) e "grande" stia per "più grande (cioè
). Invece per rendere la relazione d'ordine si usa lo strano parametro che abbiamo definito "latino/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. 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
e la "o grande" ("omega") stava per
.
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"):

- "mega" ("grande"):

- "minuscolo":

- "maiuscolo":

|
 |
|
|
|
|
|
|
|
Forti di questo schema generale, che può esserci utile anche come regola mnemonica, proviamo a scrivere, ad esempio, la definizione della seguente espressione:

Dobbiamo dire che la
è una "o-micron maiuscola" della
. Ricordiamo che:
- "micron" sta per "più piccolo", cioè
;
- "maiuscolo" sta per:
(almeno un)
tale che...
Ecco dunque la definizione cercata:
Diciamo che
se e solo se:

Infine ci interessa conoscere le implicazioni fra tutte queste relazioni. Tali implicazioni si possono ricavare immediatamente dalle seguenti considerazioni:
1) Ricordando che, in generale:

allora
è una "omicron" (cioè "più piccola") di
se e solo se
è una "omega" (cioè "più grande") di
:

2) Se una relazione è vera
allora in particolare
un certo
che la soddisfa. Dunque se una successione
è una "minuscola" della successione
allora è anche "maiuscola" di essa:

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".
 | Lo stesso argomento in dettaglio: O-grande. |
Siano
e
due funzioni definite su
a valori in
.
Si dice che
è un o grande di
, in simboli
se
.
Si dice anche che
ha ordine di grandezza minore o uguale a quello di
, cioè la funzione
domina
.
Se la successione
ha valori definitivamente diversi da zero, una condizione equivalente, sfruttando il limite superiore, è che sia
.
Si dice che
è un o-piccolo di
, in simboli
se
Si dice che
è un omega grande di
, in simboli
se
.
Si dice anche che
ha ordine di grandezza maggiore o uguale a quello di
, o che
è dominata da
.
Usando la notazione del limite inferiore, una condizione equivalente è che sia
Si dice che
è un omega piccolo di
, in simboli
se
e
sono dette avere lo stesso ordine di grandezza, in simboli
se
.
Usando i limiti superiore e inferiore, questa condizione si può enunciare come
-->
Per le espressioni asintotiche valgono le seguenti proprietà:
.
.
.
.
.
- cioè:
.
.
.
.
.
- cioè
.
.
.
- cioè
.
.
.
Oltre a queste, all'interno di ognuna delle notazioni vale la proprietà transitiva, cioè, ad esempio, se
e
allora
.
La riflessività e la transitività di
implicano che esso è un preordine, la cui relazione di equivalenza associata è proprio
. Infatti dalla definizione di
, è proprio
.
Inoltre, se
è una costante, è definitivamente
se e solo se
e analogamente è definitivamente
se e solo se
.
L'affermazione
è un o grande di
è di solito scritta come
. 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
, pensando a
come alla classe di tutte le funzioni dominate da
, o usano una notazione introdotta da Hardy, che è la seguente:
e
.
Esempio di notazione O-grande: f(x) = O(g(x)), esistono c>0 e un valore x 0 tale che a destra di x 0 si abbia f(x) < c g(x)
|
Esempio di notazione Ω-grande: f(x) = Ω(g(x)), esistono c>0 e un valore x 0 tale che a destra di x 0 si abbia f(x) > c g(x)
|