Notazione asintotica¶
Parte 3 · Notazione e crescita asintotica · Capitolo 9 · Dispensa, volume 3 (PDF) · Esercizi: Notazione asintotica
Introduzione¶
Il numero di passi eseguiti da un algoritmo è una funzione di un numero naturale: la dimensione del suo input. Due algoritmi che risolvono lo stesso problema si confrontano guardando quanto velocemente crescono queste funzioni al crescere dell'input, trascurando i fattori costanti e i valori su poche piccole istanze. In questo capitolo diamo il linguaggio preciso con cui si esprimono questi confronti: le notazioni asintotiche \(\Theta\), \(\bigO\), \(\Omega\), \(o\) e \(\omega\).
Prerequisiti. Le funzioni di variabile naturale sono le successioni del corso di Analisi Matematica 1 (fabiofurini.github.io/analisi-matematica-1/, versione inglese fabiofurini.github.io/mathematical-analysis-1/). I loro limiti, e i teoremi usati per calcolarli, non vengono rispiegati in questo capitolo: usiamo la definizione di limite e le regole di calcolo dei limiti della parte Limiti di successioni di quel corso.
Il capitolo è organizzato così.
-
Nella Sezione 9.1 definiamo le notazioni \(\Theta\), \(\bigO\) e \(\Omega\), le interpretiamo graficamente e dimostriamo che \(\Theta\) equivale a \(\bigO\) e \(\Omega\) insieme. Studiamo anche la somma e il massimo di due funzioni.
-
Nella Sezione 9.2 definiamo le notazioni \(o\) e \(\omega\), che esprimono limitazioni che non sono asintoticamente strette.
-
Nella Sezione 9.3 collegiamo le cinque notazioni al limite del rapporto \(\frac{f(n)}{g(n)}\). Quando il limite esiste, il suo valore decide quali delle cinque notazioni valgono (Proposizione 9.18, il criterio del limite); quando non esiste, si usano le definizioni.
-
Nella Sezione 9.4 dimostriamo le proprietà relazionali delle notazioni (transitività, riflessività, simmetria e simmetria trasposta), che rendono il confronto asintotico di due funzioni simile al confronto di due numeri reali, con una differenza importante.
-
Nella Sezione 9.5 vediamo come si usa la notazione nell'analisi degli algoritmi dei capitoli «Dimensione dell'input» e «Tempo di esecuzione».
Ogni costante (\(c\), \(c_1\), \(c_2\), \(n_1\)) usata negli esempi del capitolo è stata controllata numericamente con uno script, per tutti i valori di \(n\) dalla soglia \(n_1\) fino ad almeno \(2 \cdot 10^5\).
In tutto il capitolo usiamo la seguente terminologia.
Definizione 9.1: funzioni asintoticamente non negative e asintoticamente positive
Una funzione \(f\) di variabile naturale è asintoticamente non negativa se esiste \(\tilde n \in \N\) tale che \(f(n) \ge 0\) per ogni \(n \ge \tilde n\). È asintoticamente positiva se esiste \(\tilde n \in \N\) tale che \(f(n) > 0\) per ogni \(n \ge \tilde n\).
9.1 Notazioni \(\Theta\), \(\bigO\) e \(\Omega\)¶
9.1.1 Definizioni¶
Definizione 9.2: notazione \(\Theta\)
Date due funzioni \(f\) e \(g\) di variabile naturale, scriviamo \(f(n)=\Theta\big(g(n)\big)\) se esistono \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
-
Se \(f(n)= \Theta\big(g(n)\big)\), allora, per valori sufficientemente grandi di \(n\), la funzione \(f\) è limitata dall'alto e dal basso dalla funzione \(g\) moltiplicata per due costanti positive.
-
In questo caso diciamo che la funzione \(g\) è una limitazione asintotica stretta per la funzione \(f\).
-
Scriviamo \(f(n)=\Theta(1)\) per dire che i valori \(f(n)\) sono, per \(n\) sufficientemente grande, limitati dall'alto e dal basso da due costanti positive (qui \(g\) è la funzione costante \(g(n)=1\)).
Definizione 9.3: notazione \(\bigO\)
Date due funzioni \(f\) e \(g\) di variabile naturale, scriviamo \(f(n)=\bigO\big(g(n)\big)\) se esistono \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
-
Se \(f(n)= \bigO\big(g(n)\big)\), allora, per valori sufficientemente grandi di \(n\), la funzione \(f\) è limitata dall'alto dalla funzione \(g\) moltiplicata per una costante positiva.
-
In questo caso diciamo che la funzione \(g\) è una limitazione superiore asintotica per la funzione \(f\).
Definizione 9.4: notazione \(\Omega\)
Date due funzioni \(f\) e \(g\) di variabile naturale, scriviamo \(f(n)=\Omega\big(g(n)\big)\) se esistono \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
-
Se \(f(n)= \Omega\big(g(n)\big)\), allora, per valori sufficientemente grandi di \(n\), la funzione \(f\) è limitata dal basso dalla funzione \(g\) moltiplicata per una costante positiva.
-
In questo caso diciamo che la funzione \(g\) è una limitazione inferiore asintotica per la funzione \(f\).
Se \(f(n) = \Theta\big(g(n)\big)\), \(f(n) = \bigO\big(g(n)\big)\) oppure \(f(n) = \Omega\big(g(n)\big)\) allora, poiché le costanti \(c_1\) e \(c\) sono positive, si ha \(g(n) \ge 0\) e \(f(n) \ge 0\) per ogni \(n \ge n_1\) (per \(\bigO\), la disuguaglianza \(0 \le f(n) \le c\,g(n)\) dà anche \(g(n) \ge 0\)). Quindi le due funzioni \(f\) e \(g\) sono asintoticamente non negative.
-
Per dimostrare una di queste affermazioni determiniamo le costanti (\(c\), oppure \(c_1\) e \(c_2\)) e la soglia \(n_1\). In generale la soglia \(n_1\) non è la più piccola possibile e le costanti non sono uniche: anche qualunque soglia più grande, qualunque \(c_1\) più piccola e qualunque \(c_2\) più grande (o \(c\) nella definizione di \(\bigO\)) funzionano.
-
Per dimostrare che un'affermazione è falsa procediamo per assurdo: supponiamo che le costanti esistano e ricaviamo una disuguaglianza che non può valere per \(n\) arbitrariamente grande.
9.1.2 Esempi di limitazioni asintotiche strette¶
Esempio 9.1: limitazione asintotica stretta
-
Per dimostrare che
\[ - 3\: n + \frac{1}{2} \: n^2 = \Theta(n^2) \]determiniamo \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1 \: n^2 \le - 3\: n + \frac{1}{2} \: n^2 \le c_2 \: n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \frac{1}{2} - \frac{3}{n} \le c_2,\qquad \forall n \ge n_1. \]Il termine centrale cresce con \(n\) ed è sempre minore di \(\frac{1}{2}\). Quindi, scegliendo per esempio \(c_1 = \frac{1}{14}\), \(c_2=\frac{1}{2}\) e \(n_1=7\) (abbiamo scelto \(\frac{1}{14}\) poiché \(\frac{1}{14}= \frac{1}{2} - \frac{3}{7}\)), si ha
\[ 0 \le \frac{1}{14} \: n^2 \le - 3\: n + \frac{1}{2} \: n^2 \le \frac{1}{2} \: n^2,\qquad \forall n \ge 7. \]Per \(n = 6\) la limitazione inferiore non vale, poiché \(-18 + 18 = 0 < \frac{36}{14}\).
-
La dimostrazione precedente dimostra anche che
\[ - 3\: n + \frac{1}{2} \: n^2 = \bigO(n^2) \qquad\text{e}\qquad - 3\: n + \frac{1}{2} \: n^2 = \Omega(n^2). \]
Esempio 9.2: limitazione asintotica stretta
-
Per dimostrare che
\[ n^2\; (2 - \sin n) = \Theta(n^2) \]determiniamo \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1 \: n^2 \le n^2\; (2 - \sin n) \le c_2 \: n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le 2 - \sin n \le c_2,\qquad \forall n \ge n_1. \]Poiché \(-1 \le \sin n \le 1\), si ha \(1 \le 2 - \sin n \le 3\). Quindi, scegliendo per esempio \(c_1=\frac{1}{2}\), \(c_2=\frac{7}{2}\) e \(n_1=1\), si ha
\[ 0 \le \frac{1}{2}\;n^2 \le n^2\; (2 - \sin n) \le \frac{7}{2}\;n^2,\qquad \forall n \ge 1. \]
-
La dimostrazione precedente dimostra anche che
\[ n^2\; (2 - \sin n) = \bigO(n^2) \qquad\text{e}\qquad n^2\; (2 - \sin n) = \Omega(n^2). \]
9.1.3 Interpretazione grafica¶
La figura seguente dà un'interpretazione grafica delle tre notazioni.
-
In (a), da \(n_1\) in poi, i valori di \(f\) stanno fra \(c_1\,g(n)\) e \(c_2\,g(n)\); in (b) stanno sotto \(c\,g(n)\); in (c) stanno sopra \(c\,g(n)\). Prima di \(n_1\) non si richiede nulla.
-
Nella figura \(n_1\) è la soglia più piccola possibile, ma anche qualunque valore più grande andrebbe bene. La figura illustra inoltre una possibile scelta delle costanti \(c_1, c_2\) e \(c\), ma esistono altre scelte valide.
9.1.4 \(\Theta\) rispetto a \(\bigO\) e \(\Omega\)¶
Osservazione 9.5: \(\Theta\) equivale a \(\bigO\) e \(\Omega\)
Date due funzioni \(f\) e \(g\) di variabile naturale, si ha
In particolare,
Dimostrazione
Se \(f(n) = \Theta\big(g(n)\big)\), le due disuguaglianze \(0 \le f(n) \le c_2\, g(n)\) e \(0 \le c_1\, g(n) \le f(n)\) contenute in \(\eqref{eq:an-theta}\) danno \(f(n) = \bigO\big(g(n)\big)\) (con \(c = c_2\)) e \(f(n) = \Omega\big(g(n)\big)\) (con \(c = c_1\)), con la stessa soglia \(n_1\).
Viceversa, sia \(0 \le f(n) \le c'\, g(n)\) per ogni \(n \ge n_1'\), e \(0 \le c''\, g(n) \le f(n)\) per ogni \(n \ge n_1''\). Scegliendo \(c_1 = c''\), \(c_2 = c'\) e \(n_1 = \max\{n_1', n_1''\}\), otteniamo
cioè \(f(n) = \Theta\big(g(n)\big)\). □
-
Ne segue che «\(f(n) = \Theta\big(g(n)\big)\)» è una condizione sufficiente per «\(f(n) = \bigO\big(g(n)\big)\)», e «\(f(n) = \bigO\big(g(n)\big)\)» è una condizione necessaria per «\(f(n) = \Theta\big(g(n)\big)\)». Per contrapposizione si ha anche
\[ f(n) \neq \bigO\big(g(n)\big) ~~\Longrightarrow~~ f(n) \neq \Theta\big(g(n)\big). \]L'implicazione non vale nell'altro verso (si vedano i due esempi seguenti), cioè
\[ f(n) = \bigO\big(g(n)\big) ~~\nRightarrow~~ f(n) = \Theta\big(g(n)\big). \] -
Allo stesso modo, «\(f(n) = \Theta\big(g(n)\big)\)» è una condizione sufficiente per «\(f(n) = \Omega\big(g(n)\big)\)», e «\(f(n) = \Omega\big(g(n)\big)\)» è una condizione necessaria per «\(f(n) = \Theta\big(g(n)\big)\)». Per contrapposizione si ha anche
\[ f(n) \neq \Omega\big(g(n)\big) ~~\Longrightarrow~~ f(n) \neq \Theta\big(g(n)\big), \]e l'implicazione non vale nell'altro verso (si veda il terzo esempio più avanti):
\[ f(n) = \Omega\big(g(n)\big) ~~\nRightarrow~~ f(n) = \Theta\big(g(n)\big). \]
Esempio 9.3: limitazione superiore asintotica non stretta
-
Per dimostrare che
\[ 3 \: n^2 = \bigO(n^3) \]determiniamo \(c \in \R_{> 0}\) e \(n_1 \in \N\) tali che
\[ 0 \le 3\; n^2 \le c \: n^3,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^3\), questo equivale a
\[ 0 \le \frac{3}{n} \le c,\qquad \forall n \ge n_1. \]Quindi, scegliendo per esempio \(c=\frac{3}{2}\) e \(n_1=2\), si ha
\[ 0 \le 3\;n^2 \le \frac{3}{2}\;n^3,\qquad \forall n \ge 2. \](Per \(n=1\) la disuguaglianza non vale, poiché \(3 > \frac{3}{2}\).)
-
Per dimostrare che
\[ 3 \: n^2 \neq \Theta(n^3) \]procediamo per assurdo e supponiamo che esistano \(c_1 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1\; n^3 \le 3 \; n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^3\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \frac{3}{n},\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_1\) è una costante positiva (non vale per ogni \(n > \frac{3}{c_1}\)).
Esempio 9.4: limitazione superiore asintotica non stretta
-
Per dimostrare che
\[ n^2\;\sin^2 n = \bigO(n^2) \]determiniamo \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le n^2\;\sin^2 n \le c \: n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\), questo equivale a
\[ 0 \le \sin^2 n \le c,\qquad \forall n \ge n_1. \]Poiché \(0 \le \sin^2 n \le 1\), scegliendo per esempio \(c=\frac{3}{2}\) e \(n_1=1\) si ha
\[ 0 \le n^2\;\sin^2 n\le \frac{3}{2} \;n^2,\qquad \forall n \ge 1. \]
-
Per dimostrare che
\[ n^2\;\sin^2 n \neq \Theta(n^2) \]procediamo per assurdo e supponiamo che esistano \(c_1 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1\; n^2 \le n^2\;\sin^2 n,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \sin^2 n,\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_1\) è una costante positiva.1
Esempio 9.5: limitazione inferiore asintotica non stretta
-
Per dimostrare che
\[ 2 \: n^3 = \Omega(n^2) \]determiniamo \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c\; n^2 \le 2 \: n^3,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\) e poiché \(c > 0\), questo equivale a
\[ 0 < c \le 2 \;n,\qquad \forall n \ge n_1. \]Quindi, scegliendo per esempio \(c=\frac{3}{2}\) e \(n_1=1\), si ha
\[ 0 \le \frac{3}{2}\;n^2 \le 2\;n^3,\qquad \forall n \ge 1. \]
-
Per dimostrare che
\[ 2 \: n^3 \neq \Theta(n^2) \]procediamo per assurdo e supponiamo che esistano \(c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le 2\; n^3 \le c_2 \; n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\), questo equivale a
\[ 0 \le 2\;n \le c_2,\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_2\) è una costante (non vale per ogni \(n > \frac{c_2}{2}\)).
9.1.5 Somma e massimo di due funzioni¶
Osservazione 9.6: aggiungere la limitazione alla funzione
Date due funzioni \(f\) e \(g\) di variabile naturale, si ha
Dimostrazione
Se \(f(n) = \Theta\big(g(n)\big)\), esistono \(c_1, c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
Inoltre, poiché \(c_1>0\), si ha \(g(n) \ge 0\) per ogni \(n \ge n_1\). Allora, sommando \(g(n)\), otteniamo
Di conseguenza \(f(n)+g(n)= \Theta\big(g(n)\big)\), con le costanti \(c_1+1\) e \(c_2+1\) e la stessa soglia \(n_1\). □
Esempio 9.6: limitazione asintotica stretta di una somma
-
Nell'Esempio 9.1 abbiamo dimostrato che
\[ - 3\: n + \frac{1}{2} \: n^2 = \Theta(n^2) \]con \(c_1=\frac{1}{14}\), \(c_2=\frac{1}{2}\) e \(n_1=7\). Allora, per \(\eqref{eq:an-addbound}\), si ha
\[ - 3\: n + \frac{1}{2} \: n^2 + n^2 = \Theta(n^2), \]con le costanti \(c_1+1=\frac{15}{14}\), \(c_2+1=\frac{3}{2}\) e \(n_1=7\).
-
Nell'Esempio 9.2 abbiamo dimostrato che
\[ n^2\; (2 - \sin n) = \Theta(n^2) \]con \(c_1=\frac{1}{2}\), \(c_2=\frac{7}{2}\) e \(n_1=1\). Allora, per \(\eqref{eq:an-addbound}\), si ha
\[ n^2\; (2 - \sin n)+ n^2 = \Theta(n^2), \]con le costanti \(\frac{3}{2}\), \(\frac{9}{2}\) e \(n_1=1\).
-
Per l'implicazione \(\eqref{eq:an-addbound}\), l'affermazione «\(f(n) = \Theta\big(g(n)\big)\)» è una condizione sufficiente per «\(f(n) + g(n)= \Theta\big(g(n)\big)\)», e «\(f(n) + g(n)= \Theta\big(g(n)\big)\)» è una condizione necessaria per «\(f(n) = \Theta\big(g(n)\big)\)». Per contrapposizione di \(\eqref{eq:an-addbound}\) si ha anche
\[ f(n) + g(n) \neq \Theta\big(g(n)\big) ~~\Longrightarrow~~ f(n) \neq \Theta\big(g(n)\big). \]L'implicazione \(\eqref{eq:an-addbound}\) non vale nell'altro verso (si veda il controesempio seguente), cioè
\[ f(n) + g(n)= \Theta\big(g(n)\big) ~~\nRightarrow~~ f(n) = \Theta\big(g(n)\big). \]
Esempio 9.7: l'inverso dell'Osservazione 9.6 è falso
Siano \(f(n) = 10\:n\) e \(g(n) = \frac{1}{10}\:n^2\).
-
Per dimostrare che
\[ f(n) + g(n) = 10 \: n + \frac{1}{10}\: n^2 = \Theta\Big(\frac{1}{10}\:n^2\Big) = \Theta\big(g(n)\big) \]determiniamo \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1 \: \frac{1}{10}\:n^2 \le 10 \: n + \frac{1}{10}\: n^2 \le c_2 \: \frac{1}{10}\:n^2,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(\frac{1}{10}\:n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \frac{100}{n} + 1 \le c_2,\qquad \forall n \ge n_1. \]Il termine centrale decresce con \(n\) ed è sempre maggiore di \(1\); per \(n = 5\) è uguale a \(21\). Quindi, scegliendo per esempio \(c_1 = 1\), \(c_2=21\) e \(n_1=5\), si ha
\[ 0 \le \frac{1}{10} \: n^2 \le 10 \: n + \frac{1}{10}\: n^2 \le \frac{21}{10} \: n^2,\qquad \forall n \ge 5. \]
-
Per dimostrare che
\[ f(n) = 10 \: n \neq \Theta\Big(\frac{1}{10}\:n^2\Big) = \Theta\big(g(n)\big) \]procediamo per assurdo e supponiamo che esistano \(c_1 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1 \; \frac{1}{10}\:n^2 \le 10\; n ,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(\frac{1}{10}\:n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \frac{100}{n} ,\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_1\) è una costante positiva.
Quando sommiamo due funzioni, il comportamento asintotico della somma è determinato dalla maggiore delle due. Le due osservazioni seguenti lo precisano.
Osservazione 9.7: somma e massimo (1)
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente non negative, si ha
Dimostrazione
Poiché \(f\) e \(g\) sono asintoticamente non negative, esiste \(\tilde{n} \in \N\) tale che \(f(n) \ge 0\) e \(g(n) \ge 0\) per ogni \(n \ge \tilde{n}\). Allora la somma è almeno il maggiore dei due termini e al più il doppio del maggiore dei due termini:
Questo mostra che le costanti \(c_1 = 1\), \(c_2 = 2\) e \(n_1 = \tilde{n}\) soddisfano
Quindi \(f(n) + g(n) = \Theta\big( \max\{f(n), g(n)\} \big)\). □
Osservazione 9.8: somma e massimo (2)
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente non negative, si ha
Dimostrazione
Sia \(\tilde{n} \in \N\) tale che \(f(n) \ge 0\) e \(g(n) \ge 0\) per ogni \(n \ge \tilde{n}\). Il maggiore di due numeri non negativi è almeno la loro media e al più la loro somma:
Questo mostra che le costanti \(c_1 = \frac{1}{2}\), \(c_2 = 1\) e \(n_1 = \tilde{n}\) soddisfano
Quindi \(\max\{f(n), g(n)\} = \Theta\big( f(n) + g(n) \big)\). □
Esempio 9.8: somma e massimo
Per le Osservazioni 9.7 e Osservazione 9.8 si ha
In questo caso \(\max\left\{ \frac{1}{2} \: n^2 , 2^n \right\} = 2^n\) per ogni \(n \in \N\), così che \(\frac{1}{2} \: n^2 + 2^n = \Theta(2^n)\), con \(c_1=1\), \(c_2=2\) e \(n_1=0\).
9.2 Notazioni \(o\) e \(\omega\)¶
Le limitazioni asintotiche espresse dalle notazioni \(\bigO\) e \(\Omega\) possono essere o non essere asintoticamente strette. Usiamo la notazione \(o\) per indicare una limitazione superiore asintotica che non è asintoticamente stretta, e la notazione \(\omega\) per indicare una limitazione inferiore asintotica che non è asintoticamente stretta.
Esempio 9.9: limitazioni superiori asintoticamente strette e non strette
-
Si ha \(3n^3 = \bigO(n^3)\) e \(3n^3 = \Theta(n^3)\): \(n^3\) è una limitazione superiore asintotica per \(3n^3\), ed è anche una limitazione asintoticamente stretta.
-
Si ha \(3n^3 = \bigO(n^4)\) ma \(3n^3 \ne \Theta(n^4)\): \(n^4\) è una limitazione superiore asintotica per \(3n^3\), ma non è una limitazione asintoticamente stretta.
Definizione 9.9: notazione \(o\)
Date due funzioni \(f\) e \(g\) di variabile naturale, scriviamo \(f(n)=o\big(g(n)\big)\) se per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\) tale che
-
Se \(f(n)= o\big(g(n)\big)\), allora, per valori sufficientemente grandi di \(n\), la funzione \(f\) è limitata dall'alto dalla funzione \(g\) moltiplicata per qualunque costante positiva, cioè la funzione \(f\) diventa trascurabile rispetto alla funzione \(g\).
-
In questo caso diciamo che la funzione \(g\) è una limitazione superiore asintotica non stretta per la funzione \(f\).
-
La differenza con la notazione \(\bigO\) sta nel quantificatore sulla costante: per \(\bigO\) la disuguaglianza deve valere per una costante \(c\), per \(o\) deve valere per ogni costante \(c\). La soglia \(n_1\) dipende da \(c\): più piccola è \(c\), più grande è, in generale, \(n_1\).
Definizione 9.10: notazione \(\omega\)
Date due funzioni \(f\) e \(g\) di variabile naturale, scriviamo \(f(n)=\omega\big(g(n)\big)\) se per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\) tale che
-
Se \(f(n)= \omega\big(g(n)\big)\), allora, per valori sufficientemente grandi di \(n\), la funzione \(f\) è limitata dal basso dalla funzione \(g\) moltiplicata per qualunque costante positiva, cioè la funzione \(f\) diventa arbitrariamente grande rispetto alla funzione \(g\).
-
In questo caso diciamo che la funzione \(g\) è una limitazione inferiore asintotica non stretta per la funzione \(f\).
Se \(f(n) = o\big(g(n)\big)\) oppure \(f(n) = \omega\big(g(n)\big)\) allora, poiché \(c > 0\), si ha \(g(n) \ge 0\) e \(f(n) \ge 0\) per ogni \(n \ge n_1\). Quindi le due funzioni \(f\) e \(g\) sono asintoticamente non negative.
Esempio 9.10: limitazione superiore asintotica non stretta
-
Per dimostrare che
\[ 3n = o(n^2) \]dobbiamo verificare che per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\) tale che
\[ 0 \le 3n < c\, n^2, \qquad \forall n \ge n_1. \]Per \(n \ge 1\), dividendo per \(n^2\), la condizione equivale a
\[ 0 \le \frac{3}{n} < c, \qquad \forall n \ge n_1. \]Questo vale ogni volta che \(n > \frac{3}{c}\), quindi possiamo scegliere qualunque \(n_1 > \frac{3}{c}\), per esempio \(n_1 = \big\lfloor \frac{3}{c} \big\rfloor + 1\). Per esempio, \(c = 1\) dà \(n_1 = 4\), \(c = \frac{1}{2}\) dà \(n_1 = 7\) e \(c = \frac{1}{10}\) dà \(n_1 = 31\).
-
La dimostrazione precedente dimostra anche che
\[ 3n = \bigO(n^2) \](basta prendere un valore di \(c\), per esempio \(c=1\) con \(n_1=4\)).
-
Per dimostrare che
\[ 3\: n \neq \Theta(n^2) \]procediamo per assurdo e supponiamo che esistano \(c_1 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1\; n^2 \le 3 \; n,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^2\) e poiché \(c_1 > 0\), questo equivale a
\[ 0 < c_1 \le \frac{3}{n},\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_1\) è una costante positiva.
Esempio 9.11: limitazione inferiore asintotica non stretta
-
Per dimostrare che
\[ \frac{1}{5}\, n^2 = \omega(n) \]dobbiamo verificare che per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\) tale che
\[ 0 \le c\,n < \frac{1}{5}\,n^2, \qquad \forall n \ge n_1. \]Per \(n \ge 1\), dividendo per \(n\), la condizione equivale a
\[ 0 < c < \frac{1}{5}\,n, \qquad \forall n \ge n_1. \]Questo vale ogni volta che \(n > 5c\), quindi possiamo scegliere qualunque \(n_1 > 5c\), per esempio \(n_1 = \lfloor 5c \rfloor + 1\). Per esempio, \(c = 1\) dà \(n_1 = 6\) e \(c = 10\) dà \(n_1 = 51\).
-
La dimostrazione precedente dimostra anche che
\[ \frac{1}{5}\,n^2 = \Omega(n). \] -
Per dimostrare che
\[ \frac{1}{5}\,n^2 \neq \Theta(n) \]procediamo per assurdo e supponiamo che esistano \(c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le \frac{1}{5}\, n^2 \le c_2\; n,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n\), questo equivale a
\[ 0 \le \frac{n}{5} \le c_2,\qquad \forall n \ge n_1, \]che non può valere per \(n\) arbitrariamente grande, poiché \(c_2\) è una costante.
9.3 Limiti e notazioni asintotiche¶
Quando il rapporto \(\frac{f(n)}{g(n)}\) ha un limite, il suo valore ci dice subito quali notazioni valgono. In questa sezione le funzioni \(f\) e \(g\) sono asintoticamente positive, così che il rapporto è definito per ogni \(n\) sufficientemente grande. I limiti si calcolano con le regole di Analisi Matematica 1.
9.3.1 Limiti e notazioni \(o\) e \(\omega\)¶
Osservazione 9.11: limite uguale a zero
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente positive, si ha
Dimostrazione
Sia \(\tilde n \in \N\) tale che \(f(n) > 0\) e \(g(n) > 0\) per ogni \(n \ge \tilde n\).
-
Se \(\displaystyle\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =0^+\), allora per ogni \(\varepsilon \in \R_{>0}\) esiste \(n(\varepsilon)\in \N\), che possiamo prendere con \(n(\varepsilon) \ge \tilde n\), tale che
\[ 0 \le \frac{f(n)}{g(n)} < \varepsilon,\quad\forall n \ge n(\varepsilon) \qquad\Longrightarrow\qquad 0 \le f(n) < \varepsilon \; g(n), \quad\forall n \ge n(\varepsilon), \]dove abbiamo moltiplicato per \(g(n) > 0\). Scegliendo \(c = \varepsilon\) e \(n_1 = n(\varepsilon)\), questa è la definizione \(\eqref{eq:an-smallo}\), quindi \(f(n)= o\big(g(n)\big)\).
-
Se \(f(n)= o\big(g(n)\big)\), allora per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\), che possiamo prendere con \(n_1 \ge \tilde n\), tale che
\[ 0 \le f(n) < c\; g(n),\quad\forall n \ge n_1 \qquad\Longrightarrow\qquad 0 \le \frac{f(n)}{g(n)} < c, \quad\forall n \ge n_1, \]dove abbiamo diviso per \(g(n) > 0\). Poiché \(c\) è arbitrario, questa è la definizione di \(\displaystyle\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =0^+\).
□
- Se le funzioni \(f\) e \(g\) sono asintoticamente positive, «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =0^+\)» è una condizione necessaria e sufficiente per «\(f(n) = o\big(g(n)\big)\)».
Osservazione 9.12: \(o\) implica \(\bigO\)
Date due funzioni \(f\) e \(g\) di variabile naturale, si ha
Dimostrazione
La definizione \(\eqref{eq:an-smallo}\) vale per ogni \(c \in \R_{>0}\); in particolare vale per \(c=1\): esiste \(n_1 \in \N\) tale che \(0 \le f(n) < g(n) \le 1 \cdot g(n)\) per ogni \(n \ge n_1\). Questa è la definizione \(\eqref{eq:an-bigo}\) con \(c = 1\). □
-
Ne segue che «\(f(n) = o\big(g(n)\big)\)» è una condizione sufficiente per «\(f(n) = \bigO\big(g(n)\big)\)», e «\(f(n) = \bigO\big(g(n)\big)\)» è una condizione necessaria per «\(f(n) = o\big(g(n)\big)\)». Per contrapposizione di \(\eqref{eq:an-smallo-bigo}\) si ha anche
\[ f(n) \neq \bigO\big(g(n)\big) ~~\Longrightarrow~~ f(n) \neq o\big(g(n)\big). \]L'implicazione non vale nell'altro verso (si veda il controesempio seguente), cioè
\[ f(n) = \bigO\big(g(n)\big) ~~\nRightarrow~~ f(n) = o\big(g(n)\big). \]
Esempio 9.12: una limitazione superiore che non è un \(o\)
-
Per dimostrare che
\[ 3 \: n^3 = \bigO(n^3) \]determiniamo \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le 3\; n^3 \le c \: n^3,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^3\), questo equivale a
\[ 0 \le 3 \le c ,\qquad \forall n \ge n_1. \]Quindi, scegliendo per esempio \(c=\frac{7}{2}\) e \(n_1=1\), si ha
\[ 0 \le 3\;n^3 \le \frac{7}{2}\;n^3,\qquad \forall n \ge 1. \] -
Per dimostrare che
\[ 3 \: n^3 \neq o(n^3) \]calcoliamo il limite
\[ \lim_{n \rr +\infty} \frac{3\;n^3}{n^3} =3 \neq 0^+ \]e applichiamo \(\eqref{eq:an-limzero}\).
Osservazione 9.13: limite uguale a \(+\infty\)
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente positive, si ha
Dimostrazione
Sia \(\tilde n \in \N\) tale che \(f(n) > 0\) e \(g(n) > 0\) per ogni \(n \ge \tilde n\).
-
Se \(\displaystyle\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =+\infty\), allora per ogni \(\lambda \in \R_{>0}\) esiste \(n(\lambda) \in \N\), che possiamo prendere con \(n(\lambda) \ge \tilde n\), tale che
\[ \frac{f(n)}{g(n)} > \lambda ,\quad\forall n \ge n(\lambda) \qquad\Longrightarrow\qquad 0 \le \lambda \; g(n) < f(n) , \quad\forall n \ge n(\lambda). \]Scegliendo \(c = \lambda\) e \(n_1 = n(\lambda)\), questa è la definizione \(\eqref{eq:an-smallomega}\), quindi \(f(n)= \omega\big(g(n)\big)\).
-
Se \(f(n)= \omega\big(g(n)\big)\), allora per ogni \(c \in \R_{>0}\) esiste \(n_1 \in \N\), che possiamo prendere con \(n_1 \ge \tilde n\), tale che
\[ 0 \le c\; g(n) < f(n),\quad\forall n \ge n_1 \qquad\Longrightarrow\qquad \frac{f(n)}{g(n)} > c , \quad\forall n \ge n_1. \]Poiché \(c\) è arbitrario, questa è la definizione di \(\displaystyle\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =+ \infty\).
□
- Se le funzioni \(f\) e \(g\) sono asintoticamente positive, «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} =+ \infty\)» è una condizione necessaria e sufficiente per «\(f(n) = \omega\big(g(n)\big)\)».
Osservazione 9.14: \(\omega\) implica \(\Omega\)
Date due funzioni \(f\) e \(g\) di variabile naturale, si ha
Dimostrazione
La definizione \(\eqref{eq:an-smallomega}\) vale per ogni \(c \in \R_{>0}\); in particolare vale per \(c=1\): esiste \(n_1 \in \N\) tale che \(0 \le 1 \cdot g(n) < f(n)\) per ogni \(n \ge n_1\). Questa è la definizione \(\eqref{eq:an-omega}\) con \(c = 1\). □
-
Ne segue che «\(f(n) = \omega\big(g(n)\big)\)» è una condizione sufficiente per «\(f(n) = \Omega\big(g(n)\big)\)», e «\(f(n) = \Omega\big(g(n)\big)\)» è una condizione necessaria per «\(f(n) = \omega\big(g(n)\big)\)». Per contrapposizione di \(\eqref{eq:an-smallomega-omega}\) si ha anche
\[ f(n) \neq \Omega\big(g(n)\big) ~~\Longrightarrow~~ f(n) \neq \omega\big(g(n)\big). \]L'implicazione non vale nell'altro verso (si veda il controesempio seguente), cioè
\[ f(n) = \Omega\big(g(n)\big) ~~\nRightarrow~~ f(n) = \omega\big(g(n)\big). \]
Esempio 9.13: una limitazione inferiore che non è un \(\omega\)
-
Per dimostrare che
\[ 3 \: n^3 = \Omega(n^3) \]determiniamo \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c\; n^3 \le 3 \: n^3,\qquad \forall n \ge n_1. \]Con \(n \ge 1\), dividendo per \(n^3\) e poiché \(c > 0\), questo equivale a
\[ 0 < c \le 3 ,\qquad \forall n \ge n_1. \]Quindi, scegliendo per esempio \(c=\frac{5}{2}\) e \(n_1=1\), si ha
\[ 0 \le \frac{5}{2}\;n^3 \le 3\;n^3,\qquad \forall n \ge 1. \] -
Per dimostrare che
\[ 3 \: n^3 \neq \omega(n^3) \]calcoliamo il limite
\[ \lim_{n \rr +\infty} \frac{3\;n^3}{n^3} =3 \neq +\infty \]e applichiamo \(\eqref{eq:an-liminf}\).
9.3.2 Limiti e notazioni \(\Theta\), \(\bigO\) e \(\Omega\)¶
Osservazione 9.15: limite finito positivo
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente positive, si ha
Dimostrazione
Se \(\displaystyle\lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{>0}\), allora per ogni \(\varepsilon \in \R_{>0}\) esiste \(n(\varepsilon) \in \N\) tale che \(g(n) > 0\) e
Poiché \(\ell > 0\), possiamo scegliere \(\varepsilon\) abbastanza piccolo da avere \(\ell-\varepsilon >0\), per esempio \(\varepsilon = \frac{\ell}{2}\). Ponendo \(c_1=\ell-\varepsilon = \frac{\ell}{2} >0\) e \(c_2=\ell+\varepsilon = \frac{3\ell}{2} >0\), e moltiplicando per \(g(n) > 0\), si ha
e, di conseguenza, \(f(n)= \Theta\big(g(n)\big)\) con \(n_1 = n(\varepsilon)\). □
-
Ne segue che «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{> 0}\)» è una condizione sufficiente per «\(f(n) = \Theta\big(g(n)\big)\)», e «\(f(n) = \Theta\big(g(n)\big)\)» è una condizione necessaria per «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{> 0}\)». Per contrapposizione di \(\eqref{eq:an-limfinite}\) si ha anche
\[ f(n) \neq \Theta\big(g(n)\big) ~~\Longrightarrow~~ \text{il limite di } \frac{f(n)}{g(n)} \text{ non è un numero } \ell \in \R_{> 0}. \]L'implicazione non vale nell'altro verso. Un controesempio è dato dall'Esempio 9.2:
\[ n^2\; (2 - \sin n) = \Theta(n^2), \qquad\text{ma}\qquad \lim_{n \to +\infty} \frac{n^2\; (2 - \sin n)}{n^2} = \lim_{n \to +\infty} (2 - \sin n) \text{ non esiste}. \]Di conseguenza, si ha
\[ f(n) = \Theta\big(g(n)\big) ~~\nRightarrow~~ \lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{>0}. \]
È possibile che \(f(n)= \Theta\big(g(n)\big)\) anche se \(\frac{f(n)}{g(n)}\) non converge a un limite. In questo caso il criterio del limite non si può applicare, e si usa la definizione.
Esempio 9.14: limitazione asintotica stretta senza limite
Per dimostrare che
determiniamo \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
Poiché
Quindi, scegliendo per esempio \(c_1 = \frac{1}{2}\), \(c_2=\frac{7}{2}\) e \(n_1=1\), si ha
D'altra parte,
poiché il rapporto vale \(1\) per ogni \(n\) dispari e \(3\) per ogni \(n\) pari.
Osservazione 9.16: criterio del limite per \(\bigO\)
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente positive, si ha
Dimostrazione
Per le Osservazioni 9.15, Osservazione 9.5, Osservazione 9.11 e Osservazione 9.12, si ha
In entrambi i casi \(f(n)= \bigO\big(g(n)\big)\). □
-
Ne segue che «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{> 0}\) oppure \(0^+\)» è una condizione sufficiente per «\(f(n) = \bigO\big(g(n)\big)\)». Per contrapposizione di \(\eqref{eq:an-limbigo}\) si ha anche
\[ f(n) \neq \bigO\big(g(n)\big) ~~\Longrightarrow~~ \text{il limite di } \frac{f(n)}{g(n)} \text{ non è né un numero } \ell \in \R_{>0} \text{ né } 0^+. \]L'implicazione non vale nell'altro verso. Un controesempio è dato dall'Esempio 9.4:
\[ n^2\;\sin^2 n = \bigO(n^2), \qquad\text{ma}\qquad \lim_{n \to +\infty} \frac{n^2\;\sin^2 n}{n^2} = \lim_{n \to +\infty} \sin^2 n \text{ non esiste}. \]Di conseguenza, si ha
\[ f(n) = \bigO\big(g(n)\big) ~~\nRightarrow~~ \lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{> 0} \text{ oppure } 0^+. \]
È possibile che \(f(n)= \bigO\big(g(n)\big)\) anche se \(\frac{f(n)}{g(n)}\) non converge a un limite.
Osservazione 9.17: criterio del limite per \(\Omega\)
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente positive, si ha
Dimostrazione
Per le Osservazioni 9.15, Osservazione 9.5, Osservazione 9.13 e Osservazione 9.14, si ha
In entrambi i casi \(f(n)= \Omega\big(g(n)\big)\). □
-
Ne segue che «\(\lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{>0}\) oppure \(+\infty\)» è una condizione sufficiente per «\(f(n) = \Omega\big(g(n)\big)\)». Per contrapposizione di \(\eqref{eq:an-limomega}\) si ha anche
\[ f(n) \neq \Omega\big(g(n)\big) ~~\Longrightarrow~~ \text{il limite di } \frac{f(n)}{g(n)} \text{ non è né un numero } \ell \in \R_{>0} \text{ né } +\infty. \]L'implicazione non vale nell'altro verso. Un controesempio è dato dall'Esempio 9.14: poiché \((2 + (-1)^n) \: n^2 = \Theta(n^2)\), per l'Osservazione 9.5 si ha
\[ (2 + (-1)^n) \: n^2 = \Omega(n^2), \qquad\text{ma}\qquad \lim_{n \to +\infty} \frac{(2 + (-1)^n) \: n^2}{n^2} = \lim_{n \to +\infty} (2 + (-1)^n) \text{ non esiste}. \]Di conseguenza, si ha
\[ f(n) = \Omega\big(g(n)\big) ~~\nRightarrow~~ \lim_{n \rr +\infty} \frac{f(n)}{g(n)} = \ell \in \R_{>0} \text{ oppure } +\infty. \]
È possibile che \(f(n)= \Omega\big(g(n)\big)\) anche se \(\frac{f(n)}{g(n)}\) non converge a un limite.
Esempio 9.15: limitazioni asintotiche dai limiti
-
Si ha
\[ \lim_{n \rr +\infty} \frac{6\;n - n^3 + 2 \;n^4}{n^4}=\lim_{n \rr +\infty} \left( \underbrace{\frac{6}{n^3}}_{\rr 0} - \underbrace{\frac{1}{n}}_{\rr 0} + 2 \right) = 2 \in \R_{>0}. \]Allora, per \(\eqref{eq:an-limbigo}\), si ha \(6\;n - n^3 + 2 \;n^4 = \bigO(n^4)\) e, per \(\eqref{eq:an-limomega}\), si ha \(6\;n - n^3 + 2 \;n^4 = \Omega(n^4)\). Infine, per \(\eqref{eq:an-limfinite}\), si ha anche \(6\;n - n^3 + 2 \;n^4 = \Theta(n^4)\).
-
Si ha
\[ \lim_{n \rr +\infty} \frac{n+3\;n^3}{n^4} =\lim_{n \rr +\infty} \left( \underbrace{\frac{1} {n^3}}_{\rr 0} + \underbrace{\frac{3}{n}}_{\rr 0}\right)=0^+. \]Allora, per \(\eqref{eq:an-limzero}\), si ha \(n+3\;n^3=o(n^4)\). Inoltre, per \(\eqref{eq:an-smallo-bigo}\) o per \(\eqref{eq:an-limbigo}\), si ha \(n + 3\;n^3=\bigO(n^4)\).
-
Si ha
\[ \lim_{n \rr +\infty} \frac{n+3\;n^4}{n^3} = \lim_{n \rr +\infty} \left( \underbrace{\frac{1}{n^2}}_{\rr 0} + 3 \;n \right) =+\infty. \]Allora, per \(\eqref{eq:an-liminf}\), si ha \(n+3\;n^4=\omega(n^3)\). Inoltre, per \(\eqref{eq:an-smallomega-omega}\) o per \(\eqref{eq:an-limomega}\), si ha \(n+3\;n^4=\Omega(n^3)\).
9.3.3 Il criterio del limite¶
Quando il limite del rapporto esiste, le osservazioni precedenti si possono invertire: il valore del limite dice esattamente quali delle cinque notazioni valgono e quali no.
Proposizione 9.18: criterio del limite
Siano \(f\) e \(g\) due funzioni di variabile naturale asintoticamente positive tali che il limite
esista (uguale a \(0^+\), a un numero \(\ell \in \R_{>0}\), oppure a \(+\infty\)). Allora:
Dimostrazione
Le implicazioni da destra a sinistra sono \(\eqref{eq:an-limzero}\), \(\eqref{eq:an-limbigo}\), \(\eqref{eq:an-limfinite}\), \(\eqref{eq:an-limomega}\) e \(\eqref{eq:an-liminf}\), e \(\eqref{eq:an-crit-smallo}\) e \(\eqref{eq:an-crit-smallomega}\) sono \(\eqref{eq:an-limzero}\) e \(\eqref{eq:an-liminf}\). Per le altre implicazioni osserviamo prima che \(f(n)= \bigO\big(g(n)\big)\) e \(f(n)= \omega\big(g(n)\big)\) non possono valere insieme. Infatti, se \(0 \le f(n) \le c\, g(n)\) per ogni \(n \ge n_1'\), la definizione \(\eqref{eq:an-smallomega}\) con la stessa costante \(c\) dà \(n_1''\) tale che \(c\, g(n) < f(n)\) per ogni \(n \ge n_1''\), e per \(n \ge \max\{n_1', n_1''\}\) avremmo \(c\, g(n) < f(n) \le c\, g(n)\), il che è impossibile. Allo stesso modo, \(f(n)= \Omega\big(g(n)\big)\) e \(f(n)= o\big(g(n)\big)\) non possono valere insieme, perché darebbero \(c\, g(n) \le f(n) < c\, g(n)\). Poiché il limite esiste, vale esattamente uno dei tre casi \(L = 0^+\), \(L \in \R_{>0}\) e \(L = +\infty\).
-
Se \(f(n)= \bigO\big(g(n)\big)\), allora \(L \neq +\infty\), perché altrimenti \(f(n)= \omega\big(g(n)\big)\) per \(\eqref{eq:an-liminf}\). Quindi \(L = 0^+\) oppure \(L \in \R_{>0}\).
-
Se \(f(n)= \Omega\big(g(n)\big)\), allora \(L \neq 0^+\), perché altrimenti \(f(n)= o\big(g(n)\big)\) per \(\eqref{eq:an-limzero}\). Quindi \(L \in \R_{>0}\) oppure \(L = +\infty\).
-
Se \(f(n)= \Theta\big(g(n)\big)\), allora \(f(n)= \bigO\big(g(n)\big)\) e \(f(n)= \Omega\big(g(n)\big)\) per l'Osservazione 9.5, e per i due punti precedenti \(L \in \R_{>0}\).
□
Per due funzioni asintoticamente positive \(f\) e \(g\) il cui rapporto ha un limite \(L\), il criterio del limite dice:
-
se \(L = 0^+\), allora \(f(n) = o\big(g(n)\big)\) e \(f(n) = \bigO\big(g(n)\big)\), e le altre tre notazioni non valgono;
-
se \(L \in \R_{>0}\), allora \(f(n) = \Theta\big(g(n)\big)\), \(f(n) = \bigO\big(g(n)\big)\) e \(f(n) = \Omega\big(g(n)\big)\), mentre \(f(n) \neq o\big(g(n)\big)\) e \(f(n) \neq \omega\big(g(n)\big)\);
-
se \(L = +\infty\), allora \(f(n) = \omega\big(g(n)\big)\) e \(f(n) = \Omega\big(g(n)\big)\), e le altre tre notazioni non valgono.
Se il rapporto non ha limite, il criterio non si può applicare, e si usano le definizioni (Esempi 9.2 e Esempio 9.14).
Esempio 9.16: il criterio del limite
-
Nel corso di Analisi Matematica 1 (capitolo Gerarchie degli infiniti e criterio del rapporto) si dimostra che
\[ \lim_{n \rr +\infty} \frac{\ln n}{n} = 0^+. \]Per la Proposizione 9.18, si ha \(\ln n = o(n)\) e \(\ln n = \bigO(n)\), mentre \(\ln n \neq \Theta(n)\), \(\ln n \neq \Omega(n)\) e \(\ln n \neq \omega(n)\).
-
Nello stesso capitolo di quel corso si dimostra che \(\lim_{n \rr +\infty} \frac{n^2}{2^n} = 0^+\), quindi
\[ \lim_{n \rr +\infty} \frac{2^n + n^2}{2^n} = \lim_{n \rr +\infty} \Big( 1 + \underbrace{\frac{n^2}{2^n}}_{\rr\, 0^+} \Big) = 1 \in \R_{>0}. \]Per la Proposizione 9.18, si ha \(2^n + n^2 = \Theta(2^n)\), \(2^n + n^2 = \bigO(2^n)\) e \(2^n + n^2 = \Omega(2^n)\), mentre \(2^n + n^2 \neq o(2^n)\) e \(2^n + n^2 \neq \omega(2^n)\).
9.4 Proprietà relazionali delle notazioni asintotiche¶
Proposizione 9.19: proprietà relazionali
Date tre funzioni \(f\), \(g\) e \(h\) di variabile naturale, valgono le seguenti proprietà.
-
Transitività:
\[\begin{align*} &f(n)= o\big(g(n)\big) \ \text{ e } \ g(n) = o\big({h(n)}\big) ~~\Longrightarrow~~ f(n)= o\big({h(n)}\big),\\ &f(n)= \bigO\big(g(n)\big) \ \text{ e } \ g(n) = \bigO\big({h(n)}\big) ~~\Longrightarrow~~ f(n)= \bigO\big({h(n)}\big),\\ &f(n)= \Theta\big(g(n)\big) \ \text{ e } \ g(n) = \Theta\big({h(n)}\big) ~~\Longrightarrow~~ f(n)= \Theta\big({h(n)}\big),\\ &f(n)= \Omega\big(g(n)\big) \ \text{ e } \ g(n) = \Omega\big({h(n)}\big) ~~\Longrightarrow~~ f(n)= \Omega\big({h(n)}\big),\\ &f(n)= \omega\big(g(n)\big) \ \text{ e } \ g(n) = \omega\big({h(n)}\big) ~~\Longrightarrow~~ f(n)= \omega\big({h(n)}\big). \end{align*}\] -
Riflessività (per una funzione \(f\) asintoticamente non negativa):
\[ f(n)= \Theta\big(f(n)\big),\qquad f(n)= \bigO\big(f(n)\big),\qquad f(n)= \Omega\big(f(n)\big). \] -
Simmetria:
\[ f(n)= \Theta\big(g(n)\big) ~~\Longleftrightarrow~~ g(n) = \Theta\big(f(n)\big). \] -
Simmetria trasposta:
\[\begin{align*} &f(n)= \bigO\big(g(n)\big) ~~\Longleftrightarrow~~ g(n) = \Omega\big(f(n)\big),\\ &f(n)= o\big(g(n)\big) ~~\Longleftrightarrow~~ g(n) = \omega\big(f(n)\big). \end{align*}\]
Dimostrazione
Transitività. Sia \(0 \le f(n) \le c'\, g(n)\) per \(n \ge n_1'\) e \(0 \le g(n) \le c''\, h(n)\) per \(n \ge n_1''\). Allora \(0 \le f(n) \le c' c''\, h(n)\) per ogni \(n \ge \max\{n_1',n_1''\}\), e \(f(n)= \bigO\big(h(n)\big)\) con \(c = c'c'' > 0\). Le dimostrazioni per \(\Omega\) e \(\Theta\) sono uguali, con i prodotti delle costanti. Per \(o\), sia \(c \in \R_{>0}\): la definizione di \(f(n)=o\big(g(n)\big)\) con la costante \(1\) e la definizione di \(g(n)=o\big(h(n)\big)\) con la costante \(c\) danno due soglie \(n_1'\) e \(n_1''\) tali che
Poiché \(c\) è arbitraria, \(f(n)=o\big(h(n)\big)\). La dimostrazione per \(\omega\) è la stessa, con \(0 \le c\,h(n) < g(n) < f(n)\).
Riflessività. Sia \(\tilde n\) tale che \(f(n) \ge 0\) per ogni \(n \ge \tilde n\). Allora \(0 \le 1\cdot f(n) \le f(n) \le 1 \cdot f(n)\) per ogni \(n \ge \tilde n\): le definizioni di \(\Theta\), \(\bigO\) e \(\Omega\) valgono con tutte le costanti uguali a \(1\) e \(n_1 = \tilde n\).
Simmetria. Se \(0 \le c_1\, g(n) \le f(n) \le c_2\, g(n)\) per ogni \(n \ge n_1\), dividendo la disuguaglianza di sinistra per \(c_1\) e quella di destra per \(c_2\) otteniamo
cioè \(g(n) = \Theta\big(f(n)\big)\). Scambiando i ruoli di \(f\) e \(g\) otteniamo l'altro verso.
Simmetria trasposta. Si ha \(0 \le f(n) \le c\, g(n)\) se e solo se \(0 \le \frac{1}{c}\, f(n) \le g(n)\): la prima disuguaglianza definisce \(f(n)=\bigO\big(g(n)\big)\) con la costante \(c\), la seconda definisce \(g(n)=\Omega\big(f(n)\big)\) con la costante \(\frac{1}{c}\), e la soglia è la stessa. Per \(o\) e \(\omega\), sia \(f(n)=o\big(g(n)\big)\) e sia \(c \in \R_{>0}\). La definizione di \(f(n)=o\big(g(n)\big)\) con la costante \(\frac{1}{c}\) dà \(n_1\) tale che \(0 \le f(n) < \frac{1}{c}\, g(n)\), cioè \(0 \le c\, f(n) < g(n)\), per ogni \(n \ge n_1\). Poiché \(c\) è arbitraria, \(g(n)=\omega\big(f(n)\big)\). L'altro verso si dimostra allo stesso modo. □
Poiché queste proprietà relazionali valgono per le notazioni asintotiche, possiamo stabilire un'analogia fra il confronto asintotico di due funzioni e il confronto di due numeri reali \(a\) e \(b\):
-
Per due numeri reali qualsiasi \(a\) e \(b\), vale esattamente uno dei tre casi seguenti:
\[ a < b, \qquad a = b, \qquad a > b \qquad \text{(proprietà di tricotomia).} \] -
La proprietà analoga non vale per il confronto asintotico di due funzioni: esistono due funzioni \(f\) e \(g\) tali che nessuna delle cinque notazioni vale, come mostra l'esempio seguente.
Esempio 9.17: due funzioni che non si possono confrontare
Consideriamo la funzione asintoticamente positiva
e la funzione \(g(n) = n\). Per ogni \(n \ge 1\) si ha \(\frac{f(n)}{g(n)} = n^{\sin n}\). Poiché \(\pi\) è irrazionale, i valori \(n \bmod 2\pi\), \(n \in \N\), sono densi in \([0,2\pi]\). Quindi esistono interi \(n\) arbitrariamente grandi con \(\sin n > \frac12\), per i quali
e interi \(m\) arbitrariamente grandi con \(\sin m < -\frac12\), per i quali
-
Per dimostrare che
\[ n^{1 + \sin n} \neq \bigO(n), \]procediamo per assurdo e supponiamo che esistano \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che \(0 \le n^{1+\sin n} \le c\,n\), cioè \(n^{\sin n} \le c\), per ogni \(n \ge n_1\). Questo è falso per gli interi \(n\) arbitrariamente grandi con \(\sin n > \frac12\) e \(\sqrt n > c\).
-
Per dimostrare che
\[ n^{1 + \sin n} \neq \Omega(n), \]procediamo per assurdo e supponiamo che esistano \(c \in \R_{>0}\) e \(n_1 \in \N\) tali che \(0 \le c\,n \le n^{1+\sin n}\), cioè \(c \le n^{\sin n}\), per ogni \(n \ge n_1\). Questo è falso per gli interi \(m\) arbitrariamente grandi con \(\sin m < -\frac12\) e \(\frac{1}{\sqrt m} < c\).
-
Per l'Osservazione 9.5, ne segue che
\[ n^{1 + \sin n} \neq \Theta(n). \] -
Per le contrapposizioni di \(\eqref{eq:an-smallo-bigo}\) e \(\eqref{eq:an-smallomega-omega}\), ne segue anche che
\[ n^{1 + \sin n} \neq o(n) \qquad\text{e}\qquad n^{1 + \sin n} \neq \omega(n). \]La stessa conclusione segue dal limite
\[ \lim_{n \rr +\infty} \frac{ n^{1 + \sin n} }{n} = \lim_{n \rr +\infty} n^{\sin n} = \lim_{n \rr +\infty} e^{\sin n \, \ln n}, \]che non esiste (lungo gli interi \(n\) con \(\sin n > \frac12\) il rapporto tende a \(+\infty\), lungo gli interi \(m\) con \(\sin m < -\frac12\) tende a \(0^+\)): il limite non è né \(0^+\) né \(+\infty\), e applichiamo \(\eqref{eq:an-limzero}\) e \(\eqref{eq:an-liminf}\).
Quindi nessuna delle cinque notazioni vale fra \(n^{1+\sin n}\) e \(n\). Osserviamo che questo è un fallimento più forte del fallimento della tricotomia: non valgono nemmeno gli analoghi di \(a \le b\) o \(a \ge b\).
Esempio 9.18: il grafico di \(n^{1+\sin n}\)
Questo è il grafico della funzione
insieme al grafico della funzione \(g: \R_{\ge 0} \rr \R\), \(g: x \mapsto x\). I valori \(f(n)\) stanno alternativamente sopra e sotto la retta \(g\), sempre più lontani da essa.
9.5 Notazione asintotica nell'analisi degli algoritmi¶
Nei capitoli «Dimensione dell'input» e «Tempo di esecuzione» misuriamo la dimensione \(|I|\) dell'input di un algoritmo e contiamo il numero di passi \(S(n)\) che l'algoritmo esegue nel caso peggiore, in funzione di un parametro naturale \(n\). L'espressione esatta di \(S(n)\) dipende dalle convenzioni usate per contare i passi, e il tempo di un passo dipende dal calcolatore. La notazione asintotica conserva solo ciò che non dipende da questi dettagli: l'ordine di crescita.
-
I fattori costanti non contano. Se \(f(n) = \Theta\big(g(n)\big)\) e \(\lambda \in \R_{>0}\), allora \(\lambda\, f(n) = \Theta\big(g(n)\big)\), con le costanti \(\lambda c_1\) e \(\lambda c_2\) e la stessa soglia. Per esempio, un algoritmo che esegue \(4n\) passi e un algoritmo che esegue \(n\) passi hanno entrambi un numero di passi \(\Theta(n)\).
-
I termini di ordine inferiore non contano. Lo precisa l'osservazione seguente, che discende dall'Osservazione 9.7.
Osservazione 9.20: trascurare i termini di ordine inferiore
Date due funzioni \(f\) e \(g\) di variabile naturale asintoticamente non negative, si ha
Dimostrazione
Sia \(0 \le g(n) \le c\, f(n)\) per ogni \(n \ge n_1'\), e sia \(f(n) \ge 0\) per ogni \(n \ge n_1''\). Allora, per ogni \(n \ge n_1 = \max\{n_1', n_1''\}\),
cioè \(f(n) + g(n) = \Theta\big(f(n)\big)\) con le costanti \(c_1 = 1\) e \(c_2 = 1 + c\). □
Esempio 9.19: il numero di passi di due algoritmi
Nel capitolo «Tempo di esecuzione» contiamo i passi di due algoritmi su un array di \(n\) componenti.
-
FindMaximumesegue \(S(n) = 4n\) passi. Scegliendo \(c_1 = c_2 = 4\) e \(n_1 = 1\) si ha \(0 \le 4\,n \le S(n) \le 4\,n\) per ogni \(n \ge 1\), quindi \(S(n) = \Theta(n)\): il numero di passi è lineare in \(n\). -
InsertionSortesegue, nel caso peggiore,\[ S(n) = \frac{3n^2+9n-8}{2} \]passi. Per dimostrare che \(S(n) = \Theta(n^2)\) determiniamo \(c_1,c_2 \in \R_{>0}\) e \(n_1 \in \N\) tali che
\[ 0 \le c_1\, n^2 \le \frac{3n^2+9n-8}{2} \le c_2\, n^2, \qquad \forall n \ge n_1. \]Per la limitazione inferiore, \(9n - 8 \ge 0\) per ogni \(n \ge 1\), quindi \(\frac{3n^2+9n-8}{2} \ge \frac{3}{2}\, n^2\). Per la limitazione superiore, \(9n - 8 \le 9n \le 9n^2\) per ogni \(n \ge 1\), quindi \(\frac{3n^2+9n-8}{2} \le \frac{12\, n^2}{2} = 6\, n^2\). Scegliendo \(c_1 = \frac{3}{2}\), \(c_2 = 6\) e \(n_1 = 1\), si ha
\[ 0 \le \frac{3}{2}\, n^2 \le \frac{3n^2+9n-8}{2} \le 6\, n^2, \qquad \forall n \ge 1. \]Lo stesso risultato segue dal limite \(\lim_{n \rr +\infty} \frac{3n^2+9n-8}{2n^2} = \frac{3}{2} \in \R_{>0}\) e da \(\eqref{eq:an-limfinite}\). Il numero di passi è quadratico in \(n\).
-
Poiché \(n = o(n^2)\), per array grandi
InsertionSortesegue, nel caso peggiore, molti più passi diFindMaximum: per l'Osservazione 9.11, il rapporto \(\frac{4n}{(3n^2+9n-8)/2}\) tende a \(0^+\).
-
Le tre notazioni \(\bigO\), \(\Omega\) e \(\Theta\) dicono cose diverse sul numero di passi \(S(n)\) nel caso peggiore. Se \(S(n) = \bigO\big(g(n)\big)\), allora, per ogni \(n \ge n_1\), l'algoritmo esegue al più \(c\, g(n)\) passi su ogni input con parametro \(n\). Se \(S(n) = \Omega\big(g(n)\big)\), allora, per ogni \(n \ge n_1\), esiste almeno un input con parametro \(n\) su cui l'algoritmo esegue almeno \(c\, g(n)\) passi. L'affermazione \(S(n) = \Theta\big(g(n)\big)\) li fornisce entrambi, ed è la più informativa.
-
Nel capitolo «Tempo di esecuzione» l'ordine di crescita di \(S(n)\) viene poi espresso in funzione della dimensione dell'input \(|I|\), usando l'ordine di crescita di \(|I|\) ottenuto nel capitolo «Dimensione dell'input».
Riepilogo¶
-
\(f(n) = \Theta\big(g(n)\big)\), \(\bigO\big(g(n)\big)\), \(\Omega\big(g(n)\big)\): esistono costanti positive (\(c_1\) e \(c_2\), oppure \(c\)) e una soglia \(n_1\) tali che, per ogni \(n \ge n_1\), \(f(n)\) sta fra \(c_1 g(n)\) e \(c_2 g(n)\), sotto \(c\, g(n)\), sopra \(c\, g(n)\). Per dimostrare queste affermazioni si determinano le costanti.
-
\(f(n) = o\big(g(n)\big)\), \(\omega\big(g(n)\big)\): la disuguaglianza \(f(n) < c\, g(n)\), oppure \(c\, g(n) < f(n)\), vale per ogni \(c > 0\) da una soglia \(n_1\) che dipende da \(c\).
-
\(\Theta\) equivale a \(\bigO\) e \(\Omega\) insieme; \(o\) implica \(\bigO\) e \(\omega\) implica \(\Omega\). Nessuna di queste implicazioni si può invertire.
-
Criterio del limite: per funzioni asintoticamente positive il cui rapporto \(\frac{f(n)}{g(n)}\) ha un limite, decide il limite: \(0^+\) dà \(o\) e \(\bigO\), un numero \(\ell > 0\) dà \(\Theta\), \(\bigO\) e \(\Omega\), \(+\infty\) dà \(\omega\) e \(\Omega\), e in ogni caso le altre notazioni non valgono. Quando il limite non esiste, come per \(2 - \sin n\) o \(2 + (-1)^n\), si usano le definizioni.
-
Le notazioni sono transitive; \(\Theta\), \(\bigO\), \(\Omega\) sono riflessive; \(\Theta\) è simmetrica; \(\bigO\) e \(\Omega\), e \(o\) e \(\omega\), sono a simmetria trasposta. A differenza dei numeri reali, due funzioni possono non essere affatto confrontabili, come \(n^{1+\sin n}\) e \(n\).
-
Nell'analisi degli algoritmi, la notazione trascura i fattori costanti e i termini di ordine inferiore e conserva l'ordine di crescita del numero di passi.
Esercizi su questo capitolo: Notazione asintotica
-
Poiché \(\pi\) è irrazionale, i valori \(n \bmod \pi\), \(n \in \N\), sono densi in \([0,\pi]\). Quindi, per ogni \(\varepsilon \in \R_{>0}\) esistono interi \(n\) arbitrariamente grandi tali che \(|\sin n|<\varepsilon\). Scegliendo \(\varepsilon=\frac{\sqrt{c_1}}{2}\), otteniamo \(\sin^2 n < \frac{c_1}{4} < c_1\), il che contraddice \(c_1 \le \sin^2 n\) per ogni \(n\) sufficientemente grande. ↩