Notazione Theta (Θ)

---

Index

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

---

Definizione

Notazione Theta (Θ)

• Rappresenta sia il limite superiore che quello inferiore del tempo di esecuzione di un algoritmo.
• Fornisce un limite preciso sul tasso di crescita della complessità temporale dell’algoritmo man mano che la dimensione dell’input aumenta.

oss

Esempio:

• Un algoritmo ha una complessità temporale di Θ(n), significa che il tempo di esecuzione dell’algoritmo cresce linearmente con la dimensione dell’input, ma né più velocemente né più lentamente.

---

Formula

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

Ovvero

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

Se esistono tre costanti:

• $c_1>0$
• $c_2>0$
• $n_0\ge 0$

Tali che:

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

oss

$\Theta (g(n))$ rappresenta l’insieme di tutte le funzioni che hanno lo stesso ordine asintotico dalla funzione $g(n)$

---

Limite

Se il limite del rapporto $f(n)/g(n)$ per $n\to \infty$ è un numero finito $k$, allora la funzione $f(n)$ è $\Theta (g(n))$

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\ell \in (0,+\infty )⟺f(n)\in \Theta (g(n))$$

dove $\ell$ è una costante compresa tra $0$ e $+\infty$ (esclusi)

---

Calcolare g(n)

---

Verificare g(n)

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

• Limite ovvero: ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=k$
• Formula ovvero scrivere in forma:
  • $f(n)\le c_1\cdot g(n)$ trovare costanti $c_1$ e $n_0$ che la verificano
  • $f(n)\ge c_2\cdot g(n)$ trovare costanti $c_2$ e $n_0$ che la verificano
• Grafico dove dopo un certo $n_0$ la funzione $f(n)$ è sempre più grande di $g(n)$
  • ($O$) ⇒ $c_1\cdot g(n)$ sempre più grande di $f(n)$
  • ($\Omega )$ ⇒ $c_2\cdot g(n)$ sempre più piccolo di $f(n)$