Notazione Asintotica

$O(n^2)$, $\Theta(n\log n)$, $\Omega(2^n)$, $o(n)$, $w(n\log n)$

Definition 1   Diremo che una funzione $f(n)$ appartiene a $O(g(n))$ (ma chissà poi perchè si è soliti scrivere $f(n)=O(g(n))$ invece di $f(n)\in O(g(n))$) quando esistono delle costanti positive $n_0$ e $c$ tali che

$$0 \leq f(n) \leq c g(n) \mbox{\hspace{1cm} per ogni $n\geq n_0$} \mbox{\hspace{2cm} (1)}$$

Definition 2   Diremo che una funzione $f(n)$ appartiene a $\Theta(g(n))$ (ma poi si è soliti scrivere $f(n)=O(g(n))$ invece di $f(n)\in \Theta(g(n))$) quando esistono delle costanti positive $n_0$, $c_1$ e $c_2$ tali che

$$0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \mbox{\hspace{1cm} per ogni $n\geq n_0$} \mbox{\hspace{2cm} (2)}$$

Definition 3   Diremo che una funzione $f(n)$ appartiene a $\Omega(g(n))$ (ma poi si è soliti scrivere $f(n)=\Omega(g(n))$ invece di $f(n)\in \Omega(g(n))$) quando esistono delle costanti positive $n_0$ e $c$ tali che

$$0 \leq c g(n) \leq f(n) \mbox{\hspace{1cm} per ogni $n\geq n_0$} \mbox{\hspace{2cm} (3)}$$

Exercise 1   Dimostare che $2n^2 - 4n -4 = \Theta(n^2)$. Dimostare che $2n^2 - 4n -4 = O(n^2)$.

Exercise 2   È vero o falso che $f(n) = \Theta(g(n))$ implica che $f(n)=O(g(n))$? Argomentarlo. È vera anche l'implicazione inversa? Fornire un controesempio.

Exercise 3   È vero o falso che $f(n) = \Theta(g(n))$ implica che $f(n)=\Omega(g(n))$? Argomentarlo. È vera anche l'implicazione inversa? Fornire un controesempio.

Exercise 4   Dimostrare che $f(n) = \Theta(g(n))$ se e solo se abbiamo sia che $f(n)=\Omega(g(n))$ ma anche che $f(n)=O(g(n))$.

Exercise 5   Dimostrare che $f(n)=O(g(n))$ se e solo $g(n) = \Omega(f(n))$. Possiamo ora concludere, tramite l'esercizio precedente, che $f(n) = \Theta(g(n))$ se e solo se $g(n) = \Theta(f(n))$?

Definition 4   Scriveremo $f(n)=o(g(n))$ quando per una qualunque costante positiva $c$, esiste una costante positiva $n_0$ tale che

$$0 \leq f(n) \leq c g(n) \mbox{\hspace{1cm} per ogni $n\geq n_0$} \mbox{\hspace{2cm} ({\bf 1})}$$

Definition 5   Scriveremo $f(n)=\omega(g(n))$ quando per una qualunque costante positiva $c$, esiste una costante positiva $n_0$ tale che

$$0 \leq c g(n) \leq f(n) \mbox{\hspace{1cm} per ogni $n\geq n_0$} \mbox{\hspace{2cm} ({\bf 3})}$$

Exercise 6   È vero o falso che $f(n)=o(g(n))$ implica $f(n)=O(g(n))$? È vera anche l'implicazione inversa? Fornire un controesempio.

Exercise 7   È vero o falso che $f(n)=\omega(g(n))$ implica $f(n)=\Omega(g(n))$? È vera anche l'implicazione inversa? Fornire un controesempio.

Exercise 8   Dimostrare che $f(n)=o(g(n))$ se e solo $g(n) = \omega(f(n))$.

Exercise 9   Si supponga di definire $\theta(g(n))$ come l'insieme di quelle funzioni $f(n)$ tali che sia $f(n)=o(g(n))$ che $f(n)=\omega(g(n))$ valgano. Come mai siamo sicuramente dei pionieri nel proporre questa nuova classe di funzioni?

Exercise 10   Dimostrare o confutare ciascuna delle seguenti affermazioni.

• $f(n)=O(g(n))$ implica $g(n)=O(f(n))$;
• $f(n)+g(n)=\Theta(\max\{f(n),g(n)\})$;
• $f(n)=O(g(n))$ e $g(n)=O(h(n))$ implicano $f(n)=O(h(n))$;
• $f(n)=O(g(n))$ implica $2^{f(n)}=O(2^{g(n)})$;
• $f(n) = O((f(n))^2)$;
• $f(n)=\Theta(f(\frac{n}{2}))$;
• $f(n)+o(f(n))=\Theta(f(n))$.

Exercise 11   Ordinare le seguenti funzioni per ordine di crescita asintotico non decrescente. Ve ne sono alcune che presentano lo stesso ordine di crescita? $f(n)=\log \log n$, $f(n)=n^2$, $f(n)=2^{\log n}$, $f(n)=n!$, $f(n)=(\log n)!$, $f(n)=n^{\log n}$, $f(n)=2^n$, $f(n)=4^n$, $f(n)=2^{n+1}$, $f(n)=4^{\log n}$, $f(n)=2^{\log \log n}$, $f(n)=n\log n$, $f(n)=n$, $f(n)=n^3$, $f(n)=e^n$, $f(n)=(\log n)^{\log n}$, $f(n)=n^{100}$, $f(n)=(2^{\sqrt{\log n}})$,

Exercise 12   Siano $f(n)$ e $g(n)$ due funzioni asintoticamente non negative. Dimostrare che $f(n)=o(g(n))$ se e solo se $\lim_{n\mapsto \infty} \frac{f(n)}{g(n)}=0$.

Exercise 13   Siano $f(n)$ e $g(n)$ due funzioni asintoticamente non negative. Si assuma che $\lim_{n\mapsto \infty} \frac{f(n)}{g(n)}=5$. Dimostrare che $f(n)=O(g(n))$. Possiamo concludere che $f(n) = \Theta(g(n))$?

Exercise 14   Stirling riuscí finalmente a coronare i propri sforzi per l'approssimazione asintotica di $n!$ producendo la seguente formula.

$$n! = \sqrt{2\pi n} \left( \frac{n}{e} \right)^n \left( 1+ \Theta \left( \frac{1}{n} \right) \right)$$

Si utilizzi la formula di Stirling per dimostrare che $\log n! = \Theta(n\log n)$. Ottenere lo stesso risultato senza avvalersi della formula di Stirling. Possiamo concludere qualcosa sul minor numero di confronti necessario per l'ordinamento di $n$ numeri?