Esercizio 1confronto tra complessità quadratica e n log n

In questa pagina 5

Testo (scritto del 24/06/2026, parte 1, esercizio 1, 3 punti). Due algoritmi $A$ e $B$ risolvono lo stesso problema computazionale. La loro complessità al caso pessimo è $T_A(n) = \Theta(n^2)$ e $T_B(n) = \Theta(n \log n)$ , dove $n$ è la dimensione dell'input. Rispondere, motivando brevemente.

(a) È vero che esiste $n_0$ tale che, per ogni $n \ge n_0$ , l'algoritmo $B$ esegue meno operazioni di $A$ ?

(b) Uno studente afferma: "Poiché $n \log n < n^2$ , allora $B$ è sempre più veloce di $A$ ". È corretto?

(c) Un secondo studente afferma: "Se l'input diventa molto grande, la differenza tra i due algoritmi diventa trascurabile, poiché entrambi hanno tempo di esecuzione che tende a infinito". È corretto?

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 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).$

Il limite $\frac{\log n}{n}\to0$ è un caso della gerarchia degli infiniti: ogni potenza positiva di $n$ cresce più di qualunque potenza di $\log n$ (Limiti notevoli e gerarchia degli infiniti, Limiti di successioni); numericamente $\frac{\log_2 n}{n}$ vale $0{,}33$ per $n=10$ , $0{,}0066$ per $n=1000$ , $2\cdot10^{-5}$ per $n=10^6$ . 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)$ (una costante positiva: serve proprio che $o$ valga per ogni $c$ , anche per questa piccolissima) si ha, per $n$ abbastanza grande (cioè $n$ maggiore sia di $n_0$ sia delle soglie $n_1$ delle due definizioni $\Theta$ ),

$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; controllo: $1000\log_2 13746\approx 13746{,}7>13746$ mentre $1000\log_2 13747\approx 13746{,}8<13747$ , quindi $13747$ è il primo intero per cui la disuguaglianza è vera). Dalla disuguaglianza $T_B<T_A \iff 1000\,n\log_2 n < n^2 \iff 1000\log_2 n < n$ (si divide per $n>0$ ). 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.

Grafico interattivo: Controesempio del punto (b), T_A = n² e T_B = 1000·n·log₂n, in milioni di operazioni: B sta sopra A (cioè è più lento) fino a n = 13747, dove le due curve si incontrano (189 milioni di operazioni), e solo oltre diventa più veloce; a n = 1000 sono 1 contro 10 milioni

(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 è $\frac{10^6}{\log_2 10^6}=\frac{10^6}{19{,}93}\approx 5 \cdot 10^4$ ). Un algoritmo che impiegasse un secondo con $B$ ne impiegherebbe circa 14 ore con $A$ . 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$ .

Versione ripasso

Testo. $T_A = \Theta(n^2)$ , $T_B = \Theta(n \log n)$ . (a) $B$ esegue meno operazioni di $A$ per ogni $n \ge n_0$ ? (b) " $n \log n < n^2$ , quindi $B$ è sempre più veloce"? (c) "la differenza diventa trascurabile perché entrambi tendono a infinito"?

Richiamo: $T_A \in \Theta(n^2)$ vuol dire $a_1 n^2 \le T_A(n) \le a_2 n^2$ per $n \ge n_1$ , con costanti ignote (vedi Notazione asintotica).

(a) Sì. $\frac{n \log n}{n^2} = \frac{\log n}{n} \to 0$ , cioè $n \log n \in o(n^2)$ : per ogni $c > 0$ esiste $n_0$ con $n \log n \le c\,n^2$ per $n \ge n_0$ . Numericamente $\frac{\log_2 n}{n}$ vale $0{,}33$ per $n = 10$ e $0{,}0066$ per $n = 1000$ . Con $T_B \le b_2\, n \log n$ , $T_A \ge a_1 n^2$ e $c = a_1/(2b_2)$ si ottiene $T_B \le \frac{a_1}{2} n^2 < T_A$ per $n$ abbastanza grande.
(b) No. Le costanti sono nascoste in $\Theta$ . Controesempio: $T_A = n^2$ , $T_B = 1000\, n \log_2 n$ . Qui $T_B < T_A$ solo per $n \ge 13747$ ; per $n = 1000$ è $A$ a essere più veloce.
(c) No. $\frac{n^2}{n \log n} = \frac{n}{\log n} \to \infty$ : per $n = 10^6$ il rapporto vale circa $5 \cdot 10^4$ . La differenza $n^2 - n \log n$ cresce senza limite.
Errori tipici: rispondere "sì" al punto (b); scambiare "tendono entrambi a infinito" per "stesso ordine di grandezza"; dimenticare che (a) vale solo da $n_0$ in poi.