Notazione Omega (Ω)

---

Index

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

---

Definizione

Notazione Omega (Ω)

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

Esempio:

• Se un algoritmo ha una complessità temporale di Ω(n^2), significa che il tempo di esecuzione dell’algoritmo cresce almeno quadraticamente con la dimensione dell’input.

---

Formula

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

Ovvero

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

Se esistono due costanti:

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

Tali che:

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

oss

$\Omega (g(n))$ rappresenta l’insieme di tutte le funzioni che dominano dalla funzione $g(n)$

---

Limite

Se il limite del rapporto $f(n)/g(n)$ per $n\to \infty$ è positivo o infinito allora la funzione $f(n)$ è $\Omega (g(n))$

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

---

Calcolare g(n)

---

Verificare g(n)

Per Verificare verificare se $f(n)\in \Omega (g(n))$ abbiamo 3 metodi:

• Limite ovvero ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}\ne 0$
• 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)$

---