Stima asintotica

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.

Ordini di infinito

Una funzione $f$ si dice infinita in $x_0$ se il suo limite è infinito al tendere di $x$ a $x_0$. In simboli, se $\lim_{x \to x_0}|f(x)| = +\infty$. Per esempio $\frac{1}{x}$ è infinita in $0$ e $-e^{-x}$ è infinita in $-\infty$.

Una successione (che può considerarsi una funzione definita nei numeri naturali) si dice infinita se il suo limite è infinito al tendere di $n$ all'infinito. In simboli: se $\{a_n\}$ è una successione di numeri reali, $\lim_{n \to \infty}|a_n| = +\infty$. 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: $a$, $b$ e $c$ sono numeri qualunque maggiori di 1, mentre $n$ è l'indice della successione.

$\log_a{n} \le n^b \le c^n \le n! \le n^n$

Nota: il segno di $\,\le\,$ va inteso nel senso dell'o piccolo.

Altri esempi

Ecco alcuni esempi di ordini di infinito riferiti a funzioni, dove $\mathop{\mathrm{Ord}}_z$ indica l'ordine per la variabile tendente a $z$:

$\mathrm{Ord}_{+\infty} \, x^a \le \mathrm{Ord}_{+\infty} \, e^x$

$\mathrm{Ord}_0 \, \frac{1}{\sqrt x} \le \mathrm{Ord}_0 \, \frac{1} {x}$

$\mathrm{Ord}_1 \, \frac{1} {\sqrt x -1} \le \mathrm{Ord}_1 \, \frac{1}{ x -1}$

Ordini di infinitesimo

Una funzione $f$ si dice infinitesima in $x_0$ se il suo limite è $0$ al tendere di $x$ a $x_0$. In simboli, se $\lim_{x \to x_0}f(x) = 0$. Per esempio $\frac{1}{x}$ ed $e^{-x}$ sono infinitesime in $+\infty$ (la prima anche in $-\infty$).

Una successione $\{a_n\}$ si dice infinitesima quando il suo limite è uguale a zero al tendere di $n$ all'infinito:

$\lim_{n \to \infty} a_n = 0$.

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 $\le$ in $\ge$ si ha la tabella corrispondente

$\tfrac{1}{n^n} \le \tfrac{1}{n!} \le \tfrac{1}{c^n} \le \tfrac{1}{n^b} \le \tfrac{1}{\log_a n}$

Nota: l'ordine di infinitesimo di $\tfrac{1}{n^n}$ è maggiore di quello di $\tfrac{1}{n!}$, visto che quest'ultimo tende a zero più lentamente.

Altri tipi di limiti

Ecco alcuni esempi di ordini di infinitesimo riferiti a funzioni:

$\mathrm{ord}_0 \, \sqrt{x} \le \mathrm{ord}_0 \, x \le \mathrm{ord}_0 \, x^2 \le \mathrm{ord}_0 \, x^3$

$\mathrm{ord}_{-\infty} \, \frac{1}{x^n} \le \mathrm{ord}_{-\infty} \, e^x$

Successioni asintotiche

Date due successioni $a_n$ e $b_n$, esse si dicono asintotiche o asintoticamente equivalenti e lo si indica con la notazione $a_n \sim b_n$ se
$\lim_{n \to \infty} \frac{a_n} {b_n} = 1$
(Ovviamente si deve supporre che esista un $N$ tale che $b_n \not=0, \ \ \forall n \ge N$).

In questo caso è possibile creare delle catene di relazioni asintotiche:

$\mathrm{se}\, \ a_n \sim b_n \sim ... \sim c_n \ \,\mathrm{ allora }\, \ a_n \sim c_n$

Un'espressione composta da prodotto o quoziente di più fattori può essere stimata fattore per fattore:

$\mathrm{se }\, \ a_n \sim a'_n, \ b_n \sim b'_n, \ c_n \sim c'_n \ \,\mathrm{allora}\, \ \frac{a_n b_n} {c_n} \sim \frac{a'_n b'_n} {c'_n}$

La relazione $\sim$ è una relazione di equivalenza, in quanto valgono le proprietà riflessiva, commutativa e transitiva rispetto all'operatore.

Regole operative

Confronti fra infiniti e infinitesimi

Siano $a_n$ e $b_n$ due successioni infinite. Per il limite del rapporto abbiamo che se $\lim_{n\to +\infty} \frac{a_n} {b_n}$ è uguale a:

$0$:	$a_n$ è un infinito di ordine inferiore a $b_n$
$l \not= 0$:	$a_n$ e $b_n$ sono infiniti dello stesso ordine
$\pm \infty$:	$a_n$ è un infinito di ordine superiore a $b_n$
non esiste:	$a_n$ e $b_n$ non sono confrontabili.

Valgono anche le implicazioni inverse: se $a_n$ domina $b_n$ allora il limite è infinito, e così via.

Lo stesso ragionamento può essere ripetuto per gli infinitesimi. Siano $a_n$ e $b_n$ due successioni infinitesime. Per il limite del rapporto abbiamo che se $\lim_{n\to +\infty} \frac{a_n} {b_n}$ è uguale a:

$0$:	$a_n$ è un infinitesimo di ordine superiore a $b_n$
$l \not= 0$:	$a_n$ e $b_n$ sono infinitesimi dello stesso ordine
$\pm \infty$:	$a_n$ è un infinitesimo di ordine inferiore a $b_n$
non esiste:	$a_n$ e $b_n$ non sono confrontabili.

Principio di sostituzione degli infiniti

Siano $a_n$ e $b_n$ 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:

$\lim_{n \to +\infty} \frac{n^2 + \sqrt n} {5 n ^ 2 - 3 n} = \lim_{n \to +\infty} \frac{n^2} {5 n ^ 2 - 3 n} + \lim_{n \to +\infty} \frac{\sqrt n} {5 n^ 2 -3 n } = \lim_{n \to +\infty} \frac{n^2} {5 n ^ 2 } + 0 = \frac{1} {5}$

Principio di sostituzione degli infinitesimi

Siano $a_n$, $b_n$ 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:

$\lim_{n \to \infty} \frac{a_n} {b_n} = \lim_{n \to \infty} \frac{a_n + a'_n} {b_n + b'_n}$

Ad esempio:

$\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$

Principio di sostituzione degli infinitesimi equivalenti

Siano $f(x)$, $g(x)$ due funzioni infinitesime. Per il limite del rapporto $\frac{f(x)} {g(x)}$ vale

$\lim_{x \to x_0} \frac{f(x)} {g(x)} = \lim_{x \to x_0} \frac{h(x)} {k(x)}$

se risulta $f(x) \sim h(x)$ e $g(x) \sim k(x)$, cioè se numeratori e denominatori sono funzioni asintoticamente equivalenti.

Ad esempio, essendo $\tan x \sim x$:

$\lim_{x \to 0} \frac{\tan x} {\sqrt x} = \lim_{x \to 0}\frac{x} {\sqrt x} = 0$

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 $\infty$.

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 le seguente struttura:

Diciamo che la successione $f(n)$ è una $\mathrm{X}$ della successione $g(n)$, e scriviamo

$f(n) = \mathrm{X}(g(n))$

se e solo se:

$[\mathrm{quantificatore}]C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \prec \succ C |g(n)|$

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 $\forall$ ed $\exists$, mentre la $\prec \succ$ è una relazione d'ordine, e può essere $\le$ o $\ge$. Abbiamo pertanto due parametri ognuno dei quali può assumere due valori diversi, sicché le definizioni possibili saranno quattro:

	$\forall$	$\exists$
$\le$	$\forall C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \le C |g(n)|$	$\exists C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \le C |g(n)|$
$\ge$	$\forall C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \ge C |g(n)|$	$\exists C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \ge C |g(n)|$

Per distinguere questi quattro casi bisogna che anche il simbolo $\mathrm{X}(\cdot)$ che definisce la relazione fra $f(n)$ e $g(n)$ 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:

• $\mathrm{O}$ ("O grande") / $\mathrm{o}$ ("o piccolo"),
• $\Omega$ ("omega grande") / $\omega$ ("omega piccolo").

Come si vede si tratta effettivamente di quattro simboli definiti da due parametri:

• italiano/greco
• piccolo/grande

Di questi due parametri il primo, cioè "italiano/greco", viene utilizzato per specificare la relazione d'ordine, secondo la seguente associazione:

• italiano: $\le$
• greco: $\ge$

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

• piccolo: $\forall$
• grande: $\exists$

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

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"): $\le$
• "mega" ("grande"): $\ge$
• "minuscolo": $\forall$
• "maiuscolo": $\exists$

	$\forall$	$\exists$
$\le$	$\mathrm{o}$	$\mathrm{O}$
$\ge$	$\omega$	$\Omega$

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

$f(n) = \mathrm{O}(g(n))$

Dobbiamo dire che la $f(n)$ è una "o-micron maiuscola" della $g(n)$. Ricordiamo che:

• "micron" sta per "più piccolo", cioè $\le$;
• "maiuscolo" sta per: $\exists$ (almeno un) $C$ tale che...

Ecco dunque la definizione cercata:

Diciamo che $f(n) = \mathrm{O}(g(n))$ se e solo se:

$\exists C \ \exists N \colon \ \ \ \ \forall n > N, \ \ |f(n)| \le C |g(n)|$

Infine ci interessa conoscere le implicazioni fra tutte queste relazioni. Tali implicazioni si possono ricavare immediatamente dalle seguenti considerazioni:

1) Ricordando che, in generale:

$a \le b \ \Leftrightarrow \ b \ge a$

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

$f(x) = \mathrm{O} / \mathrm{o}(g(x)) \ \Leftrightarrow \ g(x) = \Omega / \omega (f(x))$

2) Se una relazione è vera $\forall C$ allora in particolare $\exists$ un certo $C$ che la soddisfa. Dunque se una successione $f(n)$ è una "minuscola" della successione $g(n)$ allora è anche "maiuscola" di essa:

$f(x) = \mathrm{o}/\omega(g(x)) \ \Rightarrow \ f(x) = \mathrm{O} / \Omega (g(x))$

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

Per approfondire, vedi O-grande.

Siano $f$ e $g$ due funzioni definite su $\N$ a valori in $\R$.

Si dice che $f(n)$ è un o grande di $g(n)$, in simboli

$f(n) = \mathrm{O}(g(n))$

se $\exists c > 0, n_0 \in N \colon \ \ \ \ \forall n \ge n_0, \ \ |f(n)| \le c |g(n)|$.

Si dice anche che $f(n)$ ha ordine di grandezza minore o uguale a quello di $g(n)$, cioè la funzione $g(n)$ domina $f(n)$.

Se la successione $g(n)$ ha valori definitivamente diversi da zero, una condizione equivalente, sfruttando il limite superiore, è che sia $\limsup_{n \to \infty} \left| \frac{f(n)} {g(n)} \right| < \infty$.

Esempi

$n = \mathrm{O}(2n)$

$n = \mathrm{O}( \frac{n} {2} )$

$4n^2 + n = \mathrm{O}(n^2)$

$n \log n \neq \mathrm{O}(n)$

O piccolo

Si dice che $f(n)$ è un o-piccolo di $g(n)$, in simboli

$f(n) = \mathrm{o}(g(n))$

se $\lim_{n \to \infty} \frac{f(n)} {g(n)} = 0$

Omega grande

Si dice che $f(n)$ è un omega grande di $g(n)$, in simboli

$f(n) = \Omega(g(n))$

se $\exists c >0, n_0 \in \N\colon \ \ \ \ \forall n \ge n_0, \ \ |f(n)| \geq c |g(n)|$.

Si dice anche che $f(n)$ ha ordine di grandezza maggiore o uguale a quello di $g(n)$, o che $g(n)$ è dominata da $f(n)$.

Usando la notazione del limite inferiore, una condizione equivalente è che sia $\liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0$

Omega piccolo

Si dice che $f(n)$ è un omega piccolo di $g(n)$, in simboli

$f(n) = \omega(g(n))$

se $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Theta

$f(n)$ e $g(n)$ sono dette avere lo stesso ordine di grandezza, in simboli

$f(n) = \Theta(g(n))$

se $\exists c_1,c_2 > 0, n_0 \in \N \colon \ \ \ \ \forall n \ge n_0, \ \ c_1 |g(n)| \leq |f(n)| \leq c_2 |g(n)|$.

Usando i limiti superiore e inferiore, questa condizione si può enunciare come $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$ -->

Proprietà delle espressioni asintotiche

Per le espressioni asintotiche valgono le seguenti proprietà:

Proprietà di base

1. $f = \mathrm{O}(g) \iff g = \Omega(f)$.
2. $f = \mathrm{o}(g) \iff g = \omega(f)$.
3. $f = \mathrm{O}(f)$ .
4. $f = \mathrm{o}(f) \ \Rightarrow \ f \equiv 0$.

Implicazioni

1. $g = \mathrm{o}(f) \ \Rightarrow \ g = \mathrm{O}(f)$.

   cioè: $o(f) \subseteq \mathrm{O}(f)$.

2. $f = \mathrm{O}(g) \ \not \Rightarrow \ f = \mathrm{o}(g)$.

Somme di funzioni

1. $\mathrm{O}(f) + \mathrm{O}(g) = \mathrm{O}(\max \lbrace |f|,|g| \rbrace)$.
2. $\mathrm{O}(k g) = \mathrm{O}(g), \ \forall k \in \R_0$.
3. $\mathrm{O}(f) + \mathrm{O}(f) = \mathrm{O}(f)$.

   cioè $g=\mathrm{O}(f) \land h=\mathrm{O}(f) \ \Rightarrow g+h = \mathrm{O}(f)$.

4. $\mathrm{O}(f) + \mathrm{o}(f) = \mathrm{O}(f)$.
5. $\mathrm{o}(f) + \mathrm{o}(f) = \mathrm{o}(f)$.

Prodotti

1. $\mathrm{O}(f) \mathrm{O}(g) = \mathrm{O}(f g)$

   cioè $h=\mathrm{O}(f) \land k=\mathrm{O}(g) \ \Rightarrow h k = \mathrm{O}(f g)$.

2. $\mathrm{O}(f) \mathrm{o}(g) = \mathrm{o}(f g)$.
3. $\mathrm{o}(f) \mathrm{o}(g) = \mathrm{o}(f g)$.

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

La riflessività e la transitività di $\mathrm{O}$ implicano che esso è un preordine, la cui relazione di equivalenza associata è proprio $\Theta$. Infatti dalla definizione di $\Theta$, è proprio $f = \Theta(g)\iff f=\mathrm{O}(g)\land g=\mathrm{O}(f)$.

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

Problemi di notazione

L'affermazione $f(x)$ è un o grande di $g(x)$ è di solito scritta come $f(x)=\mathrm{O}(g(x))$. Questo è un leggero abuso di notazione, in quanto non si sta asserendo l'uguaglianza delle due funzioni. Inoltre la proprietà non è simmetrica:

$\mathrm{O}(x) = \mathrm{O}(x^2) \ \ \mathrm{ ma } \ \ \mathrm{O}(x^2)\ne \mathrm{O}(x)$.

Per questa ragione, alcuni autori preferiscono una notazione insiemistica e scrivono $f \in \mathrm{O}(g)$, pensando a $\mathrm{O}(g)$ come alla classe di tutte le funzioni dominate da $g$, o usano una notazione introdotta da Hardy, che è la seguente:

$f\lesssim g \iff f \in \mathrm{O}(g)$   e   $f\ll g \iff f\in \mathrm{o}(g)$.

Grafici

Esempio di notazione O-grande: f(x) = O(g(x)), esistono c>0 e un valore x0 tale che a destra di x0 si abbia f(x) < c g(x)

Esempio di notazione Ω-grande: f(x) = Ω(g(x)), esistono c>0 e un valore x0 tale che a destra di x0 si abbia f(x) > c g(x)

Voci correlate

• Limite di una successione
• Limite di una funzione
• Limite notevole
• Teoria della complessità computazionale
• Algoritmo