Esercizio 1confronto tra complessità quadratica e n log n

---

Richiami

$T_A \in \Theta(n^2)$ significa che esistono costanti positive $a_1, a_2, n_1$ con $a_1 n^2 \le T_A(n) \le a_2 n^2$ per $n \ge n_1$; analogamente per $T_B$ con $b_1 n \log n \le T_B(n) \le b_2 n \log n$ (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 →). Le costanti non sono note: la notazione le nasconde.

(a) Sì

Si confronta il limite del rapporto:

$$\frac{n \log n}{n^2} = \frac{\log n}{n} \xrightarrow[n \to \infty]{} 0, \qquad \text{quindi } n \log n \in o(n^2).$$

Per definizione di $o$, per ogni costante $c > 0$ esiste $n_0$ tale che $n \log n \le c\,n^2$ per $n \ge n_0$. Allora, fissate le costanti nascoste, $T_B(n) \le b_2\, n \log n$ e $T_A(n) \ge a_1 n^2$: scegliendo $c = a_1 / (2 b_2)$ si ha, per $n$ abbastanza grande,

$$T_B(n) \le b_2\, n \log n \le b_2 \cdot \frac{a_1}{2 b_2}\, n^2 = \frac{a_1}{2}\, n^2 < a_1 n^2 \le T_A(n).$$

Quindi da un certo $n_0$ in poi $B$ esegue strettamente meno operazioni di $A$: $B$ è asintoticamente più efficiente.

(b) No

$n \log n < n^2$ è un confronto tra le funzioni che descrivono solo l'andamento. Le complessità vere sono $\Theta(\cdot)$ di queste funzioni, cioè moltiplicate per costanti ignote. Controesempio: $T_A(n) = n^2$ e $T_B(n) = 1000\, n \log_2 n$ rispettano le ipotesi, ma $T_B(n) < T_A(n)$ solo se $1000 \log_2 n < n$, cioè per $n \ge 13747$ (calcolato con un piccolo programma). Per $n$ più piccoli, ad esempio $n = 1000$, $A$ fa $10^6$ operazioni e $B$ circa $10^7$: $A$ è più veloce. Conclusione: la superiorità di $B$ vale per $n$ sufficientemente grande, non sempre. L'analisi asintotica ignora le costanti e può essere fuorviante per input piccoli.

(c) No

Il fatto che entrambi i tempi tendano a infinito non implica che la differenza sia trascurabile; conta il rapporto:

$$\frac{n^2}{n \log n} = \frac{n}{\log n} \xrightarrow[n \to \infty]{} \infty.$$

All'aumentare di $n$ il tempo di $A$ diventa infinitamente più grande di quello di $B$ (per esempio per $n = 10^6$ il rapporto è circa $5 \cdot 10^4$). Anche la differenza assoluta $n^2 - n \log n$ cresce senza limite. L'affermazione è falsa.

Errori comuni

• Rispondere "sì" al punto (b): $n \log n < n^2$ dice solo come crescono le funzioni, non il tempo reale.
• Confondere "tendono entrambi a infinito" con "hanno lo stesso ordine di grandezza".
• Nel punto (a) dimenticare che l'affermazione è su $n$ abbastanza grande, non su tutti gli $n$.