Notazione asintotica

Si considerano funzioni $f, g : \mathbb{N} \to \mathbb{R}$ positive per $n$ abbastanza grande. L'analisi asintotica ignora i fattori moltiplicativi costanti e i termini additivi non dominanti (vedi Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →).

Le quattro definizioni

Le costanti $c$ ed $n_0$ non dipendono da $n$. Per $o$ vale invece "per ogni $c$", e $n_0$ dipende da $c$.

Esempi con le costanti

• $3n + 4 \in O(n)$ con $c = 7$, $n_0 = 1$ (perché $3n + 4 \le 3n + 4n$ per $n \ge 1$); anche con $c = 4$ e $n_0 = 4$: $3n + 4 \le 4n \iff n \ge 4$.
• $n + 2n^2 \in O(n^2)$ con $c = 3$, $n_0 = 1$.
• $3n + 4 \in O(n^2)$ con $c = 4$, $n_0 = 4$ (vero ma poco informativo: non è un limite stretto).
• $2^{100} \in O(1)$ con $c = 2^{100}$.
• $3n + 4 \in \Omega(n)$ con $c = 3$; $6n^2 + 1 \in \Omega(n)$ con $c = 6$.
• $100 n \in o(n^2)$: per ogni $c$ si prende $n_0 = 100/c$.
• $3n/\log_2 n \in o(n)$ perché il rapporto $3/\log_2 n \to 0$.

Proprietà

1. Polinomi: $\sum_{i=0}^{k} a_i n^i \in \Theta(n^k)$ se $a_k > 0$ e $k, a_i$ costanti. Per $O$ si prende $c = \sum |a_i|$, $n_0 = 1$. Per $\Omega$ si pone $\gamma = \max_{i<k}|a_i|$ e si usa che $\sum_{i<k} a_i n^i \ge -k\gamma n^{k-1}$, da cui per $n \ge 2k\gamma/a_k$ si ottiene $\ge \frac{a_k}{2} n^k$. Esempio: $(n+1)^5 \in \Theta(n^5)$.
2. Polinomio contro esponenziale: $n^k \in o(a^n)$ se $k > 0$, $a > 1$ (limite $n^k/a^n \to 0$).
3. Logaritmo contro potenza: $(\log_b n)^k \in o(n^h)$ per $b > 1$, $k, h > 0$. Si pone $m = \log_b n$: $n^h = (b^h)^m$ con $a = b^h > 1$ e $m^k \in o(a^m)$ per il punto 2.
4. Cambio di base: $\log_b n = \log_a n \cdot \log_b a$, quindi $\log_b n \in \Theta(\log_a n)$ per basi costanti. Dentro la notazione la base si omette; fuori si assume $2$. Inoltre $a^{\log_2 n} = n^{\log_2 a}$.
5. Legami tra notazioni:
   • $f \in o(g) \Rightarrow f \in O(g)$ (si prende $c = 1$);
   • $f \in O(g) \iff g \in \Omega(f)$ (si divide per $c$);
   • $f \in O(g)$ e $g \in O(f) \Rightarrow f \in \Theta(g)$;
   • $f \in O(g) \Rightarrow f + g \in \Theta(g)$ (perché $g \le f + g \le (c+1)g$);
   • non valgono: $O \Rightarrow o$ ($f = g = n$) né $O \Rightarrow \Theta$ ($f = n$, $g = n^2$).

Sommatorie notevoli

$$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}, \qquad \sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \in \Theta(n^3), \qquad \sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}\ (a \ne 1).$$

Utili anche $\lfloor x \rfloor$ (più grande intero $\le x$), $\lceil x \rceil$ (più piccolo intero $\ge x$) e $x \bmod y$ (resto della divisione intera, % in C): $39 \bmod 7 = 4$.

Terminologia

Ordine crescente: $1 \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n$.

Esempio svolto

Un algoritmo su un array $X$ di $n$ interi esegue $c_1 n$ operazioni per ogni intero pari e $c_2 \lceil \log_2 n \rceil$ per ogni dispari. Nel caso peggiore tutti gli elementi sono pari: $n \cdot c_1 n = c_1 n^2$ (più costanti), quindi $\Theta(n^2)$. Limite superiore: ogni elemento costa al più $\max(c_1 n, c_2 \lceil \log_2 n \rceil) \le c' n$, totale $\le c' n^2$. Inferiore: l'istanza di soli pari costa $c_1 n^2$.

Errori comuni

• Confondere "è $O(n^2)$" con "è quadratico": $O$ è solo un limite superiore, $3n + 4 \in O(n^2)$ è vero ma non stretto; per "esattamente" serve $\Theta$.
• Dire che $f \in O(g)$ implica $f \in \Theta(g)$, o che $O$ implica $o$.
• Far dipendere $c$ o $n_0$ da $n$.
• Dimenticare che $\log$ senza base fuori dalla notazione è in base 2.