Notazione Big O (O)

---

Index

1. Definizione
2. Formula
3. Limite
4. Calcolare g(n)
5. Flip Flop

---

Definizione

Notazione Big O

• Rappresenta il limite superiore o lo scenario peggiore del tempo di esecuzione di un algoritmo.
• Fornisce un limite superiore sul tasso di crescita della complessità temporale dell’algoritmo man mano che la dimensione dell’input aumenta.

oss

Calcolare il limite superiore di un algoritmo ci permette di scoprire il costo che l’algoritmo non supererà mai

Esempio:

• Un algoritmo ha una complessità temporale di O(n), significa che il tempo di esecuzione dell’algoritmo cresce linearmente con la dimensione dell’input.

---

Formula

$$O(g(n))=\{f(n):\exists c>0,n_0\ge 0t.c.f(n)\le c\cdot g(n)\forall n\ge n_0\}$$

Ovvero

$f(n)\in O(g(n))$

Se esistono due costanti:

• $c>0$
• $n_0\ge 0$

Tali che:

• $f(n)\le c\cdot g(n)$ per ogni $n\ge n_0$

oss

$O(g(n))$ rappresenta l’insieme di tutte le funzioni dominate dalla funzione $g(n)$

---

Limite

Se il limite del rapporto $f(n)/g(n)$ per $n\to +\infty$ è diverso da $+\infty$ allora la funzione $f(n)$ è $O(g(n))$

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}\ne +\infty ⟺f(n)\in O(g(n))$$

---

Calcolare g(n)

---

Verificare g(n)

Per verificare verificare $f(n)\in O(g(n))$ abbiamo 3 metodi:

• Limite ovvero: ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}\ne +\infty$
• Formula ovvero: Scrivere in forma $f(n)\le c\cdot g(n)$ e trovare costanti $c$ e $n_0$ che la verificano
• Grafico dove dopo un certo $n_0$ la funzione $g(n)$ è sempre più grande di $f(n)$