Esercizio 2relazioni tra O, o, Omega e Theta

---

Richiami

Definizioni (vedi Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →), per $n$ abbastanza grande:

• $f \in O(g)$: $f(n) \le c\,g(n)$ per una costante $c > 0$;
• $f \in \Omega(g)$: $f(n) \ge c\,g(n)$ per una costante $c > 0$;
• $f \in o(g)$: $f(n) \le c\,g(n)$ per ogni costante $c > 0$ (equivale a $\lim f/g = 0$);
• $f \in \Theta(g)$: $O$ e $\Omega$ insieme.

Prima versione

(a) Vera. $f \in o(g)$ vale per ogni $c > 0$, in particolare per $c = 1$: esiste $n_0$ con $f(n) \le 1 \cdot g(n)$ per $n \ge n_0$. Questa è esattamente la definizione di $f \in O(g)$.

(b) Falsa. Controesempio: $f(n) = g(n) = n$. Vale $f \in O(g)$ (con $c = 1$), ma $\frac{f(n)}{g(n)} = 1 \not\to 0$, quindi $f \notin o(g)$. $O$ permette lo stesso ordine di grandezza, $o$ no.

(c) Vera. Da $f \in O(g)$: $f(n) \le c_1 g(n)$. Da $g \in O(f)$: $g(n) \le c_2 f(n)$, cioè $\frac{1}{c_2} g(n) \le f(n)$. Dunque $\frac{1}{c_2}\, g(n) \le f(n) \le c_1\, g(n)$ per $n$ abbastanza grande: $f \in \Theta(g)$.

Seconda versione

(a) Vera. Da $f(n) \le c\,g(n)$ si ottiene $g(n) \ge \frac1c f(n)$, quindi $g \in \Omega(f)$ con costante $\frac1c$.

(b) Falsa in generale. $f \in O(g)$ dà solo un limite superiore per $f$. Controesempio: $f(n) = n$, $g(n) = n^2$: $f \in O(g)$ ma $f \notin \Omega(g)$ (il rapporto $f/g = 1/n \to 0$), quindi $f \notin \Theta(g)$.

(c) Vera. Per $n \ge n_0$ vale $f(n) \le c\,g(n)$, e poiché $f, g > 0$: $g(n) \le f(n) + g(n) \le (c + 1)\,g(n)$. Quindi $f + g \in \Theta(g)$ con costanti $1$ e $c + 1$. (Esempio: $n + n^2 \in \Theta(n^2)$.)

Errori comuni

• Leggere $O$ come "uguale a meno di costanti": $O$ è solo un limite superiore.
• Scambiare $o$ e $O$: $o$ richiede $\lim f/g = 0$, quindi esclude $f = g$.
• Dimenticare di scrivere un controesempio esplicito dove l'affermazione è falsa.