Master Theorem - enunciato, casi e applicazioni

Il Master Theorem (MT) dà l'ordine di grandezza delle soluzioni di una classe importante di ricorrenze, senza risolverle esplicitamente. Ha una struttura più ristretta della formula generaleL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →: si ottiene da essa. Prima la versione semplificata (con prova), poi la generalizzazione.

Enunciato

Siano $a, T_0 > 0$, un intero $b > 1$ e $w(n) : \mathbb{Z}^+ \to \mathbb{Z}^+$ non decrescente. Si consideri, per $n = b^k$, $$T(n) = \begin{cases} T_0 & n = 1 \\ a\,T(n/b) + w(n) & n > 1. \end{cases} \tag{$\ast$}$$ È la formula generale con $s(n) = a$, $f(n) = n/b$, $n_0 = 1$. La funzione di soglia (threshold) è $n^{\log_b a}$.

Teorema (Master Theorem). La soluzione di $(\ast)$ soddisfa $$T(n) = \begin{cases} > \Theta\bigl(n^{\log_b a}\bigr) & \text{se } \exists\,\varepsilon > 0 : w(n) = O\bigl(n^{\log_b a - \varepsilon}\bigr) \quad \text{(Caso 1)} \\[4pt] > \Theta\bigl(n^{\log_b a}\log n\bigr) & \text{se } w(n) = \Theta\bigl(n^{\log_b a}\bigr) \quad \text{(Caso 2)} \\[4pt] > \Theta\bigl(w(n)\bigr) & \text{se } \begin{cases} \exists\,\varepsilon > 0 : w(n) = \Omega\bigl(n^{\log_b a + \varepsilon}\bigr) \\ \exists\,c \in \mathbb{R},\ 0 < c < 1 : \forall n \quad a\,w(n/b) \le c\,w(n) \end{cases} \quad \text{(Caso 3)} > \end{cases}$$

La condizione del Caso 3 con $c$ è la condizione di regolarità: $w$ cresce "senza sbalzi". Per le funzioni naturali del corso (i polinomi) vale sempre (vedi sotto). Come sempre, i logaritmi di base costante dentro l'ordine di grandezza si scrivono senza base (differiscono per una costante moltiplicativa; Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →).

Il MT non è esaustivo. Esistono parametri che non rientrano in nessun caso. Esempio: $a = 1$, $b = 2$, $w(n) = \log_2 n$: la soglia è $n^{\log_2 1} = n^0 = 1$ e $w$ è asintoticamente maggiore, quindi potrebbe applicarsi solo il Caso 3; ma $\forall \varepsilon > 0$ si ha $\lim_{n\to\infty}\frac{\log_2 n}{n^\varepsilon} = 0$ (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 →), quindi $\log_2 n$ non è mai $\Omega(n^{\varepsilon})$ e il Caso 3 non vale. Sul confronto con la soglia: la differenza deve essere una potenza polinomiale $n^\varepsilon$, non un fattore logaritmico.

Prova

Passo preliminare. Per funzioni positive a dominio intero, $O$ e $\Omega$ si possono dichiarare valide per tutti gli $n > 0$ (non solo da un $\bar n$ in poi). Se $w(n) \le c\,g(n)$ per $n > \bar n$, si pone $\bar c = \max\{c,\ w(1)/g(1),\ \dots,\ w(\bar n)/g(\bar n)\}$: per $1 \le n \le \bar n$, $w(n) = \frac{w(n)}{g(n)}g(n) \le \bar c\,g(n)$, e per $n > \bar n$, $w(n) \le c\,g(n) \le \bar c\,g(n)$. Analogamente, per $\Omega$ si usa $\hat c = \min\{c,\ w(1)/g(1),\ \dots,\ w(\hat n)/g(\hat n)\}$.

Il punto di partenza. Con la formula generale ($s = a$, $f = n/b$, $n_0 = 1$, $f^\ast(n,1) = \log_b n - 1$, $a^\ell$ nodi al livello $\ell$ di taglia $n/b^\ell$) e l'identità $a^{\log_b n} = n^{\log_b a}$: $$T(n) = \sum_{\ell=0}^{\log_b n - 1} a^\ell\, w\!\left(\frac{n}{b^\ell}\right) + n^{\log_b a}\,T_0. \tag{$\ast\ast$}$$ Il secondo termine è $\Theta(n^{\log_b a})$ perché $T_0 > 0$: stesso ordine della soglia. Resta da studiare la somma nei tre casi.

Caso 1. Da $w(n) = O(n^{\log_b a - \varepsilon})$ segue $\exists\,\bar c > 0$ con $w(n) \le \bar c\,n^{\log_b a - \varepsilon}$ per ogni $n > 0$. Usando $(b^\ell)^{\log_b a} = a^\ell$: $$\begin{aligned} \sum_{\ell=0}^{\log_b n - 1} a^\ell\, w\!\left(\tfrac{n}{b^\ell}\right) &\le \bar c \sum_{\ell=0}^{\log_b n - 1} a^\ell \left(\frac{n}{b^\ell}\right)^{\log_b a - \varepsilon} = \bar c \sum_{\ell=0}^{\log_b n - 1} \frac{a^\ell\, n^{\log_b a - \varepsilon}}{a^\ell\, b^{-\ell\varepsilon}} \\ &= \bar c\, n^{\log_b a - \varepsilon}\sum_{\ell=0}^{\log_b n - 1} (b^\varepsilon)^\ell = \bar c\, n^{\log_b a - \varepsilon}\,\frac{b^{\varepsilon\log_b n} - 1}{b^\varepsilon - 1} = \bar c\, n^{\log_b a - \varepsilon}\,\frac{n^\varepsilon - 1}{b^\varepsilon - 1} \\ &\le \frac{\bar c}{b^\varepsilon - 1}\, n^{\log_b a}. \end{aligned}$$ La somma è dunque $O(n^{\log_b a})$ e $T(n) = O(n^{\log_b a}) + \Theta(n^{\log_b a}) = \Theta(n^{\log_b a})$. Se $T_0 = 0$ si ha solo $T(n) = O(n^{\log_b a})$. Per $T_0 > 0$ la soluzione vale anche con lavoro nullo $w = 0$: allora l'unico lavoro è sulle foglie.

Caso 2. Da $w(n) = \Theta(n^{\log_b a})$ si ha $\hat c\,n^{\log_b a} \le w(n) \le \bar c\,n^{\log_b a}$ per ogni $n > 0$. Il termine $a^\ell\, (n/b^\ell)^{\log_b a} = a^\ell n^{\log_b a}/a^\ell = n^{\log_b a}$ non dipende da $\ell$: ogni livello costa lo stesso. Quindi $$\sum_{\ell=0}^{\log_b n - 1} a^\ell\, w\!\left(\tfrac{n}{b^\ell}\right) \le \bar c\,n^{\log_b a}\sum_{\ell=0}^{\log_b n - 1}1 = \bar c\,n^{\log_b a}\log_b n,$$ e allo stesso modo $\ge \hat c\,n^{\log_b a}\log_b n$. Quindi la somma è $\Theta(n^{\log_b a}\log n)$ e, aggiungendo $\Theta(n^{\log_b a})$, $T(n) = \Theta(n^{\log_b a}\log n)$.

Caso 3. Si dimostra prima che la regolarità implica $a^\ell w(n/b^\ell) \le c^\ell\, w(n)$ per ogni $\ell \ge 0$, per induzione su $\ell$:

• [B] $\ell = 0$: banale.
• [HP] vera per i valori minori di $\ell > 0$.
• [TH] $a^\ell w(n/b^\ell) = a^{\ell-1}\cdot a\cdot w\!\left(\frac{n/b^{\ell-1}}{b}\right) \le a^{\ell-1}\,c\,w(n/b^{\ell-1})$ (regolarità con $n' = n/b^{\ell-1}$), $= c\cdot a^{\ell-1}w(n/b^{\ell-1}) \le c\cdot c^{\ell-1}w(n) = c^\ell w(n)$ (per [HP]).

Allora, con la serie geometrica di ragione $c < 1$, $$\sum_{\ell=0}^{\log_b n - 1} a^\ell\, w\!\left(\tfrac{n}{b^\ell}\right) \le w(n)\sum_{\ell=0}^{\log_b n - 1}c^\ell < w(n)\sum_{\ell=0}^{\infty}c^\ell = \frac{w(n)}{1 - c},$$ quindi la somma è $O(w(n))$ e $T(n) = O(w(n)) + \Theta(n^{\log_b a}) = O(w(n))$, perché la soglia è dominata da $w(n) = \Omega(n^{\log_b a + \varepsilon})$. Per il limite inferiore, per $n > 1$, $T(n) = a\,T(n/b) + w(n) \ge w(n)$ (somma di contributi non negativi): $T(n) = \Omega(w(n))$. I due limiti danno $T(n) = \Theta(w(n))$. $\square$

Che cosa dice il MT sul progetto. Nel Caso 1 domina il lavoro alle foglie: per migliorare occorre ridurre il numero di foglie, per esempio le sottoistanze generate dal Divide (è ciò che fa l'algoritmo di StrassenStrassen calcola il prodotto n x n con 7 chiamate ricorsive invece di 8, usando 10 somme/sottrazioni nel divide e 8 nel conquer: T(n) = 7T(n/2) + (9/2)n^2, Theta(n^(log2 7)) con soluzione esatta 7n^(log2 7) - 6n^2; la costante 7 è più che tripla di quella dell'iterativo (2) e Strassen batte l'iterativo solo da n = 655 (per le potenze di 2, da 1024). L'ibridazione cambia il caso base (iterativo per n <= n0): costo n^(log2 7)(2n0+5)/n0^(log2 7 - 2) - 6n^2, minimo per n0 = 8 con costante ~3.92.Algoritmo di Strassen e ibridazione →). Nel Caso 3 domina il lavoro dell'istanza principale: occorre ridurre quel lavoro. Il Caso 2 corrisponde a una strategia bilanciata, con lo stesso contributo da ogni livello: per migliorare serve spesso una diversa e più efficiente proprietà di sottostruttura.

La versione estesa

Una prova più complessa (si rimanda al libro di testo) mostra che i tre casi valgono identici anche per $$T(n) = \begin{cases} a\,T(\lfloor n/b\rfloor) + w(n) & n > n_0 \\ T_0 & n \le n_0 \end{cases} \qquad\text{e}\qquad T(n) = \begin{cases} a\,T(\lceil n/b\rceil) + w(n) & n > n_0 \\ T_0 & n \le n_0 \end{cases}$$ per valori arbitrari di $n$ e di $n_0$. Arrestare la ricorrenza a $n_0 > 1$ sostituisce ogni sottoalbero di profondità e costo costanti con la costante $T_0$, e questo può cambiare solo le costanti moltiplicative, non l'ordine di grandezza. Per questo, quando si usa il MT si adotta la convenzione di scrivere solo la relazione implicita, $$T(n) = a\,T(n/b) + w(n),$$ senza arrotondamenti. È una convenzione da usare solo per applicare il MT: altrove quella scrittura non ha senso (Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →).

Come si applica

1. Si leggono $a$ (numero di sottoistanze), $b$ (fattore di riduzione) e $w(n)$.
2. Si calcola la soglia $n^{\log_b a}$.
3. Si confronta $w(n)$ con la soglia per esponente: se $w$ è polinomiale $\Theta(n^k)$, i casi sono $k < \log_b a$ (Caso 1), $k = \log_b a$ (Caso 2), $k > \log_b a$ (Caso 3).
4. Nel Caso 3 si verifica la regolarità, cioè si trova $c < 1$ con $a\,w(n/b) \le c\,w(n)$.

Regolarità per i polinomi. Se $w(n) = n^k$ e siamo nel Caso 3, per un $\varepsilon > 0$ è $k \ge \log_b a + \varepsilon$. Allora $$a\,w(n/b) = a\left(\frac nb\right)^k = \frac{a}{b^k}\,n^k = \frac{a}{b^k}\,w(n) \le \frac{a}{b^{\log_b a + \varepsilon}}\,w(n) = \frac{a}{a\,b^\varepsilon}\,w(n) = \frac{1}{b^\varepsilon}\,w(n),$$ perché $b^{\log_b a} = a$: basta $c = b^{-\varepsilon} < 1$. Per un lavoro polinomiale la regolarità vale sempre.

Esempi di applicazione

I casi MAX e merge sort, in dettaglio: per MAX $a = 2$, $b = 2$, $w = 1$; la soglia è $n^{\log_2 2} = n$ e con $\varepsilon = 1$ si ha $w = 1 = O(n^{1-\varepsilon}) = O(1)$: Caso 1, $T = \Theta(n)$. Per merge sort $w(n) = n - 1 = \Theta(n)$: Caso 2, $T = \Theta(n\log n)$. L'algoritmo per le matrici ARB del compito del 19 giugno 2024 (prodotto con tre moltiplicazioni ricorsive) ha $T(n) = 3T(n/2) + 3n$: Caso 1.

Regolarità nei due Casi 3 della tabella: per $T(n/2) + n$ si ha $1\cdot\frac n2 = \frac12\,n$, quindi $c = \frac12$; per $3T(n/4) + n^2$ si ha $3\left(\frac n4\right)^2 = \frac{3}{16}\,n^2$, quindi $c = \frac3{16}$.

Un controllo numerico (rapporto tra $T(n)$ esatto per $n = 2^k$ e la soglia, che tende a una costante):

from functools import lru_cache

def rapporto(a, b, w, T0, k, scala):
    @lru_cache(None)
    def T(n): return T0 if n == 1 else a * T(n // b) + w(n)
    n = b**k
    return T(n) / scala(n)

# 3T(n/4) + n^2, T(1) = 1:  T(n) / n^2  ->  16/13 = 1.2307...
print(rapporto(3, 4, lambda n: n*n, 1, 10, lambda n: n*n))
# 7T(n/2) + n^2:  T(n) / n^(log2 7)  ->  7/3 = 2.333...
import math
print(rapporto(7, 2, lambda n: n*n, 1, 20, lambda n: n**math.log2(7)))

Uso non corretto del MT

Va usato verificando sempre le condizioni dei tre casi. Per $T(n) = 2T(n/2) + n\log_2 n$: soglia $n^{\log_2 2} = n$; poiché $w(n) = n\log n = \omega(n)$ i primi due casi non si applicano. Per il Caso 3 servirebbe $n\log n = \Omega(n^{1+\varepsilon})$ per un $\varepsilon > 0$, ma $\log n / n^\varepsilon \to 0$: la condizione non è soddisfatta e il MT non si può applicare. Applicarlo comunque (Caso 3) darebbe $\Theta(n\log n)$, che è errato. Lo si vede srotolando con $n = 2^k$ (formula generale, $T_0 = 1$, $w(n) = n\log_2 n$): $$T(n) = \sum_{\ell=0}^{\log_2 n-1}2^\ell\cdot\frac{n}{2^\ell}\log_2\frac{n}{2^\ell} + n = \sum_{\ell=0}^{\log_2 n - 1}n\,(\log_2 n - \ell) + n = n\sum_{\ell'=1}^{\log_2 n}\ell' + n,$$ con il cambio di indice $\ell' = \log_2 n - \ell$ (per $\ell = 0..\log_2 n - 1$, $\ell'$ va da $\log_2 n$ a $1$) e la somma di Gauss $\sum_{\ell'=1}^{m}\ell' = \frac{m(m+1)}{2}$ (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →): $$T(n) = n\,\frac{\log_2 n\,(\log_2 n + 1)}{2} + n = \Theta\bigl(n\log^2 n\bigr),$$ un ordine di grandezza più grande (di un fattore $\log n$) di quello ottenuto con il MT usato male. Verifica: per $T(1) = 1$ si ha $T(2) = 2T(1) + 2 = 4 = 2\cdot\frac{1\cdot2}{2} + 2$, $T(4) = 2\cdot4 + 8 = 16 = 4\cdot\frac{2\cdot3}{2} + 4$.

Errori comuni

• Applicare il Caso 3 con $w$ maggiore della soglia di un fattore solo logaritmico (come $n\log n$ contro $n$): serve $n^\varepsilon$.
• Dimenticare di verificare la regolarità nel Caso 3, oppure verificarla con un $c \ge 1$.
• Confondere $a$ e $b$ (la soglia è $n^{\log_b a}$, non $n^{\log_a b}$).
• Applicare il MT a ricorrenze con sottoistanze di taglie diverse, come $T(n/2) + T(n/3) + n$: servono un limite superiore $T'$ con taglie uguali (Esercizio - ricorrenza con parti intere, Master Theorem e induzione parametrica (simulazione d'esame 2025-26, es. 1)) o la formula generale.
• Usare la scrittura $T(n) = aT(n/b) + w(n)$, senza arrotondamenti, al di fuori del MT.

Domande d'esame

1. Enunciare il Master Theorem e dire che cosa domina il costo nei tre casi. Risposta: confronto tra $w(n)$ e $n^{\log_b a}$; Caso 1 foglie, Caso 2 tutti i livelli ugualmente (e un fattore $\log n$), Caso 3 radice (istanza principale).
2. Dare l'ordine di grandezza di $T(n) = 3T(n/4) + n^2$. Soglia $n^{\log_4 3}$; $n^2 = \Omega(n^{\log_4 3+1})$ e regolarità con $c = 3/16$: Caso 3, $\Theta(n^2)$.
3. Si può applicare il MT a $T(n) = 2T(n/2) + n\log n$? Qual è la soluzione? No (né Caso 2 né 3: $n\log n$ non è $\Theta(n)$ né $\Omega(n^{1+\varepsilon})$); srotolando $T(n) = \Theta(n\log^2 n)$.