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$, Limiti di successioniUna successione ha limite l se, da un certo indice in poi, i suoi termini stanno vicini a l quanto si vuole; definizioni con epsilon, limiti infiniti e unicità.Limiti di successioni →);
• $f \in \Theta(g)$: $O$ e $\Omega$ insieme.

Prima versione

Prima di rispondere conviene avere due esempi di riferimento: $f=n$, $g=n^2$ ($f\in o(g)$, quindi anche $O(g)$, ma non $\Theta$) e $f=n$, $g=2n$ ($f\in O(g)$ e $\Theta(g)$, ma non $o(g)$ perché $f/g=\frac12\not\to0$).

(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 (il più grande dei due $n_0$): $f \in \Theta(g)$. Esempio: $f=3n+1$, $g=n$: $f\le 4g$ per $n\ge1$ e $g\le f$, quindi $\frac11 g\le f\le4g$.

Seconda versione

(a) Vera. Da $f(n) \le c\,g(n)$ si ottiene, dividendo per $c>0$, $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$ (la prima disuguaglianza perché $f>0$; la seconda perché $f+g\le c\,g+g=(c+1)g$). (Esempio: $n + n^2 \in \Theta(n^2)$: $n^2\le n+n^2\le2n^2$ per $n\ge1$.)

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.