Le notazioni asintotiche saranno un oggetto che useremo sempre nel corso, per esprimere in maniera sintetica il comportamento (a livello di complessità di tutti gli algoritmi che presenteremo).

Sono 5 quelle a cui faremo riferimento di cui 3 le più importanti che utilizzeremo in maniera più diffusa

La notazione $O$

Def: Una funzione $f : \N \rarr \N$ è detta "$O$ grande" di una funzione $g: \N \rarr \N$, $f(n)=O(g(n))$, se esistono un intero $n_0$ e una costante $c > 0$ per cui

$\forall x > n_0, f(n)\leq cg(n)$

Informalmente, $f(n)=O(g(n))$ indica che f è "dominata" da g (il grafico di f sta sotto quello di g)

Esempio:

• $n=O(2n) \text{ per } c=1, n_0=0$
• $n=O(\cfrac{n}{2}) \text{ per } c=2, n_0=0$
• $4n^2+n=O(n^2) \text{ per }c=5, n_0=0$
• $n log(n) \neq O(n)$ perchè $log(n) \leq c$ (la funzione log(n) cresce, quindi non è ≤ di una costante → questa disuguaglianza non è mai verificata per infiniti valori

Questa notazione ci dice solo un "tetto massimo" oltre il quale non si va

→ la useremo per esprimere un "tetto massimo" nell'allocazione di risorse

La notazione $\Omega$

Una funzione $f:\N\rarr\N$ è detta w-grande di una funzione $g:\N\rarr\N$

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

se esistono un interno $n_0$ e una costante $c>0$ per cui