Il Master theorem

Parte 5 · Ricorsione · Capitolo 16 · Dispensa, volume 5 (PDF) · Esercizi: Il Master theorem · App: Il Master theorem

Introduzione

Nel capitolo Equazioni di ricorrenza abbiamo risolto ricorrenze per espansione, per sostituzione e con gli alberi di ricorsione. Ogni metodo richiede qualche calcolo, e per le ricorrenze divide et impera il calcolo è sempre lo stesso: disegnare l'albero, sommare i costi dei livelli, confrontare la radice con le foglie. Alla fine di quel capitolo abbiamo osservato tre possibili comportamenti: dominano le foglie, tutti i livelli costano uguale, oppure domina la radice.

Il Master theorem trasforma questi tre comportamenti in un risultato pronto all'uso. In questo capitolo

• richiamiamo le ricorrenze in forma standard e gli algoritmi che le producono (Sezione 16.1);

• enunciamo il teorema e ne spieghiamo i tre casi (Sezione 16.2);

• lo applichiamo con uno schema fisso in cinque passi a molti esempi (Sezione 16.3), e mostriamo le situazioni in cui non può essere applicato (Sezione 16.4);

• lo dimostriamo (Sezione 16.5), prima per potenze esatte di \(b\) e poi per ogni numero naturale.

16.1 Ricorrenze in forma standard

• Nel capitolo Equazioni di ricorrenza abbiamo visto che il numero di passi eseguiti da un algoritmo ricorsivo è descritto naturalmente da una equazione di ricorrenza, cioè un'equazione che esprime il valore di una funzione su un input di dimensione \(n\) in termini dei suoi valori su input più piccoli.

• Una grande famiglia di algoritmi divide et impera produce ricorrenze di una forma molto specifica, detta forma standard:

  \[ \blue{T(n) = a\, T\left(\frac{n}{b}\right) + f(n)} \]

  dove:

  • \(n\) è la dimensione dell'input;

  • \(a\) è il numero di sottoproblemi generati da ciascuna chiamata ricorsiva (\(a \ge 1\), costante);

  • \(\frac{n}{b}\) è la dimensione di ciascun sottoproblema (\(b > 1\), costante); quando \(n/b\) non è un numero naturale si intende \(\lfloor n/b \rfloor\) oppure \(\lceil n/b \rceil\);

  • \(f(n)\) è il costo di dividere il problema negli \(a\) sottoproblemi e di combinare le loro soluzioni (tutto ciò che viene fatto al di fuori delle chiamate ricorsive). Supponiamo sempre che \(f(n)\) sia asintoticamente positiva, cioè \(f(n)>0\) per ogni \(n\) sufficientemente grande.

• Per \(n\) sufficientemente piccolo (per esempio \(n=1\)) la ricorsione si ferma e \(T(n)=\Theta(1)\): risolvere un problema di dimensione costante richiede un numero costante di passi. Per questo motivo il caso base di solito non viene nemmeno scritto.

In questo capitolo una ricorrenza è un oggetto matematico: usiamo una generica funzione \(T(n)\). Quando analizziamo un algoritmo ricorsivo, la funzione descritta dalla ricorrenza è il numero di passi \(S(n)\) eseguiti nel caso peggiore su un input di parametro di dimensione \(n\); il tempo di esecuzione nel caso peggiore \(T(|I|)\) si ottiene poi da \(S(n)\) esattamente come nel capitolo Tempo di esecuzione.

• Esempi di ricorrenze in forma standard (saranno tutte risolte nella Sezione 16.3):

  Algoritmo	Ricorrenza	\(a\)	\(b\)	\(f(n)\)
  Ricerca binaria (ricorsiva)	\(T(n)=T(n/2)+1\)	\(1\)	\(2\)	\(1\)
  Somma di un array (ricorsiva)	\(T(n)=2T(n/2)+1\)	\(2\)	\(2\)	\(1\)
  Merge sort	\(T(n)=2T(n/2)+n\)	\(2\)	\(2\)	\(n\)
  Moltiplicazione di Karatsuba	\(T(n)=3T(n/2)+n\)	\(3\)	\(2\)	\(n\)
  Moltiplicazione di matrici di Strassen	\(T(n)=7T(n/2)+n^2\)	\(7\)	\(2\)	\(n^2\)

• Il Master theorem fornisce l'ordine di grandezza di \(T(n)\) per la maggior parte delle ricorrenze in forma standard, direttamente da \(a\), \(b\) e \(f(n)\), senza alcun calcolo sulla ricorsione.

16.2 Il Master theorem

Teorema 16.1: Master theorem

Siano \(a \ge 1\) e \(b>1\) costanti, sia \(f(n)\) una funzione asintoticamente positiva, e sia \(T(n)\) definita sui numeri naturali dalla ricorrenza

\[ T(n) = a\, T\left(\frac{n}{b}\right) + f(n), \]

dove \(n/b\) è interpretato come \(\lfloor n/b\rfloor\) oppure \(\lceil n/b\rceil\), e \(T(n)=\Theta(1)\) per \(n\) sufficientemente piccolo. Allora \(T(n)\) ha le seguenti limitazioni asintotiche.

• Caso 1: se \(f(n) = O\big(n^{\log_b a - \epsilon}\big)\) per qualche costante \(\epsilon>0\), allora

  \[ \blue{T(n)=\Theta\big(n^{\log_b a}\big)}; \]

• Caso 2: se \(f(n) = \Theta\big(n^{\log_b a}\log^k n\big)\) per qualche costante \(k\ge 0\), allora

  \[ \blue{T(n)=\Theta\big(n^{\log_b a}\log^{k+1} n\big)}; \]

• Caso 3: se \(f(n) = \Omega\big(n^{\log_b a + \epsilon}\big)\) per qualche costante \(\epsilon>0\), e se

  \[ a\, f\left(\frac{n}{b}\right) \le c\, f(n) \]

  per qualche costante \(c<1\) e per ogni \(n\) sufficientemente grande (condizione di regolarità), allora

  \[ \blue{T(n)=\Theta\big(f(n)\big)}. \]

• Questo è l'enunciato classico del teorema (come nel libro di testo di Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms), con il caso 2 esteso: per \(k=0\) si ottiene l'enunciato di base “se \(f(n)=\Theta(n^{\log_b a})\) allora \(T(n)=\Theta(n^{\log_b a}\log n)\)”.

• Le notazioni \(O\), \(\Omega\) e \(\Theta\) dell'enunciato sono quelle definite nel capitolo 9 «Notazione asintotica».

• La dimostrazione è data nella Sezione 16.5.

16.2.1 Regola pratica

• In ciascuno dei tre casi confrontiamo la funzione \(f(n)\) con la funzione

  \[ n^{\log_b a}, \]

  che (come vedremo nel Lemma 16.3) è il numero di foglie dell'albero di ricorsione. Come regola pratica, si controlli:

  \[ n^{\log_b a } \quad \begin{cases} \text{polinomialmente più grande di } f(n) & \longrightarrow \quad \text{\red{caso 1}:}\quad T(n)=\Theta\big(n^{\log_b a}\big)\\[2mm] \text{dello stesso ordine di } f(n) \text{ (a meno di } \log^k n) &\longrightarrow \quad \text{\red{caso 2}:}\quad T(n)=\Theta\big(n^{\log_b a}\log^{k+1} n\big) \\[2mm] \text{polinomialmente più piccolo di } f(n) & \longrightarrow \quad \text{\red{caso 3}:}\quad T(n)=\Theta\big(f(n)\big) \end{cases} \]

  e si determini di conseguenza l'ordine di grandezza di \(T(n)\) (se possibile).

• Intuitivamente, la più grande tra le due funzioni determina la soluzione della ricorrenza.

• Polinomialmente più piccola (più grande) significa più piccola (più grande) di un fattore \(n^{\epsilon}\) per qualche costante \(\epsilon>0\). Per esempio:

  • \(n\) è polinomialmente più piccolo di \(n^2\) (fattore \(n^1\)), e \(n^{2}\) è polinomialmente più piccolo di \(n^{2.1}\) (fattore \(n^{0.1}\));

  • \(n\) è più piccolo di \(n\log n\), ma non polinomialmente più piccolo: per ogni \(\epsilon>0\)

    \[ \lim_{n\to\infty}\frac{n\log n}{n^{1+\epsilon}}=\lim_{n\to\infty}\frac{\log n}{n^{\epsilon}} = 0^+, \]

    quindi \(n\log n\) cresce più lentamente di \(n\cdot n^{\epsilon}\), qualunque \(\epsilon>0\) scegliamo.

16.2.2 Intuizione

• Srotolando la ricorrenza (si veda l'albero di ricorsione nella Figura 16.1) il costo totale è

  \[ T(n) = \underbrace{\Theta\big(n^{\log_b a}\big)}_{\text{costo delle foglie}} \; + \; \underbrace{\sum_{j=0}^{\log_b n -1} a^j f\left(\frac{n}{b^j}\right)}_{\text{costo dei livelli interni}} \]

  dove il livello \(j\) dell'albero contiene \(a^j\) sottoproblemi di dimensione \(n/b^j\).

• Consideriamo il caso semplice \(f(n)=n^d\). Il costo del livello \(j\) è

  \[ a^j \left(\frac{n}{b^j}\right)^{d} = n^d\left(\frac{a}{b^d}\right)^{j}, \]

  quindi i costi dei livelli formano una progressione geometrica di ragione \(a/b^d\). Poiché \(a/b^d>1 \iff d<\log_b a\):

  • caso 1 (\(d<\log_b a\)): i costi dei livelli crescono geometricamente dalla radice alle foglie; il totale è dominato dalle foglie, cioè da \(n^{\log_b a}\);

  • caso 2 (\(d=\log_b a\)): tutti i \(\log_b n\) livelli hanno lo stesso costo \(n^{d}=n^{\log_b a}\); il totale è \(n^{\log_b a}\) per il numero di livelli, cioè \(n^{\log_b a}\log n\);

  • caso 3 (\(d>\log_b a\)): i costi dei livelli decrescono geometricamente; il totale è dominato dalla radice, cioè da \(f(n)\).

16.2.3 I vuoti tra i casi

• I tre casi non coprono tutte le possibili funzioni \(f(n)\).

  • C'è un vuoto tra il caso 1 e il caso 2 quando \(f(n)\) è più piccola di \(n^{\log_b a}\) ma non polinomialmente più piccola (e non della forma \(n^{\log_b a}\log^k n\) con \(k\ge0\)), per esempio \(f(n)=n^{\log_b a}/\log n\).

  • C'è un vuoto tra il caso 2 e il caso 3 quando \(f(n)\) è più grande di \(n^{\log_b a}\) ma non polinomialmente più grande (e non della forma \(n^{\log_b a}\log^k n\)), per esempio \(f(n)=n^{\log_b a}\, 2^{\sqrt{\log_2 n}}\).

  • Il caso 3 non si applica anche quando \(f(n)\) è polinomialmente più grande di \(n^{\log_b a}\) ma la condizione di regolarità non vale.

• In queste situazioni il Master theorem non può essere usato, e la ricorrenza deve essere risolta con altre tecniche (albero di ricorsione, iterazione, metodo di sostituzione), si veda la Sezione 16.4.

16.2.4 Una nota sulla base dei logaritmi

• Poiché \(\log_c n = \dfrac{\log_2 n}{\log_2 c}\) per ogni base \(c>1\), abbiamo

  \[ \log_c^k n = \frac{1}{\log_2^k c}\,\log_2^k n = \Theta\big(\log_2^k n\big). \]

  Quindi, dentro \(\Theta\), \(O\) e \(\Omega\) la base del logaritmo è irrilevante: nel caso 2 scriviamo semplicemente \(\log^k n\).

• Al contrario, la base \(b\) nell'esponente \(n^{\log_b a}\) è essenziale: per esempio \(n^{\log_2 4}=n^2\) mentre \(n^{\log_4 4}=n\), e \(n^{2}\neq\Theta(n)\).

• Il Master theorem confronta il costo della radice, \(f(n)\), con il numero di foglie dell'albero di ricorsione, \(n^{\log_b a}\): la più grande tra le due determina \(T(n)\); quando sono dello stesso ordine (a meno di \(\log^k n\)) compare un ulteriore fattore \(\log n\).

• “Più grande” e “più piccola” devono essere polinomiali (di un fattore \(n^\epsilon\)); nel caso 3 deve valere anche la condizione di regolarità.

• Quando \(f(n)\) cade in un vuoto tra i casi, il teorema non dà alcuna risposta.

16.3 Applicare il Master theorem

Per risolvere una ricorrenza con il Master theorem seguiamo sempre questo schema:

1. identificare \(a\), \(b\) e \(f(n)\) (e controllare che \(a\ge 1\), \(b>1\) siano costanti e \(f(n)\) sia asintoticamente positiva);

2. calcolare \(n^{\log_b a}\);

3. confrontare \(n^{\log_b a}\) con \(f(n)\) e ipotizzare il caso;

4. verificare l'ipotesi del caso: trovare \(\epsilon>0\) (caso 1 o 3), trovare \(k\ge0\) (caso 2), e controllare la condizione di regolarità (caso 3);

5. concludere.

Cominciamo con tre ricorrenze, una per ciascun caso, e poi risolviamo le ricorrenze degli algoritmi elencati nella Sezione 16.1.

Esempio 16.1: \(T(n)=16\,T(n/4)+n\)

1. \(a=16\), \(b=4\), \(f(n)=n\).

2. \(n^{\log_b a}=n^{\log_4 16}=n^2\).

3. \(n^2\) è polinomialmente più grande di \(f(n)=n\) \(\longrightarrow\) caso 1.

4. \(f(n)=n=O\big(n^{2-\epsilon}\big)\) con \(\epsilon=1\).

5. \(T(n)=\Theta\big(n^{\log_4 16}\big)=\Theta(n^2)\).

Esempio 16.2: \(T(n)=8\,T(n/2)+n^3\)

1. \(a=8\), \(b=2\), \(f(n)=n^3\).

2. \(n^{\log_b a}=n^{\log_2 8}=n^3\).

3. \(n^3\) e \(f(n)=n^3\) hanno lo stesso ordine \(\longrightarrow\) caso 2.

4. \(f(n)=n^3=\Theta\big(n^{3}\log^k n\big)\) con \(k=0\).

5. \(T(n)=\Theta\big(n^{3}\log^{k+1} n\big)=\Theta(n^3\log n)\).

Esempio 16.3: \(T(n)=8\,T(n/3)+n^2\)

1. \(a=8\), \(b=3\), \(f(n)=n^2\).

2. \(n^{\log_b a}=n^{\log_3 8}\approx n^{1.893}\).

3. \(n^{1.893}\) è polinomialmente più piccolo di \(f(n)=n^2\) \(\longrightarrow\) caso 3.

4. \(f(n)=n^2=\Omega\big(n^{\log_3 8+\epsilon}\big)\) per ogni \(0<\epsilon\le 2-\log_3 8\approx 0.107\).
   Condizione di regolarità: cerchiamo una costante \(c<1\) tale che, per ogni \(n\) grande,

   \[ 8\, f\left(\frac{n}{3}\right) \le c\, f(n) \quad\Longleftrightarrow\quad 8\left(\frac{n}{3}\right)^2 \le c\, n^2 \quad\Longleftrightarrow\quad \frac{8}{9}\, n^2 \le c\, n^2 , \]

   che vale per ogni \(c\) con \(\frac{8}{9}\le c<1\), per esempio \(c=\frac{8}{9}\).

5. \(T(n)=\Theta(n^2)\).

Esempio 16.4: Ricerca binaria: \(T(n)=T(n/2)+1\)

1. \(a=1\), \(b=2\), \(f(n)=1\).

2. \(n^{\log_b a}=n^{\log_2 1}=n^0=1\).

3. \(1\) e \(f(n)=1\) hanno lo stesso ordine \(\longrightarrow\) caso 2.

4. \(f(n)=1=\Theta\big(n^{0}\log^k n\big)\) con \(k=0\).

5. \(T(n)=\Theta\big(n^{0}\log n\big)=\Theta(\log n)\).

Esempio 16.5: Merge sort (ordinamento per fusione): \(T(n)=2\,T(n/2)+n\)

1. \(a=2\), \(b=2\), \(f(n)=n\).

2. \(n^{\log_b a}=n^{\log_2 2}=n\).

3. \(n\) e \(f(n)=n\) hanno lo stesso ordine \(\longrightarrow\) caso 2.

4. \(f(n)=n=\Theta\big(n\log^k n\big)\) con \(k=0\).

5. \(T(n)=\Theta(n\log n)\).

Esempio 16.6: Somma di un array: \(T(n)=2\,T(n/2)+1\)

1. \(a=2\), \(b=2\), \(f(n)=1\).

2. \(n^{\log_b a}=n^{\log_2 2}=n\).

3. \(n\) è polinomialmente più grande di \(f(n)=1\) \(\longrightarrow\) caso 1.

4. \(f(n)=1=O\big(n^{1-\epsilon}\big)\) con \(\epsilon=1\) (infatti \(n^{1-1}=n^0=1\)).

5. \(T(n)=\Theta(n)\).

La somma ricorsiva di un array che divide l'array in due metà (l'algoritmo RecursiveSum del capitolo «Algoritmi ricorsivi») è un algoritmo di questo tipo.

Ogni chiamata esegue una quantità costante di lavoro al di fuori delle chiamate ricorsive, e il numero totale di chiamate è \(\Theta(n)\): contandole (nei notebook Colab del capitolo), su \(n=8\), \(1000\) e \(2^{20}=1\,048\,576\) elementi otteniamo \(15\), \(1\,999\) e \(2\,097\,151\) chiamate, cioè esattamente \(2n-1\).

Esegui in Colab:PythonC++Java

Esempio 16.7: Karatsuba: \(T(n)=3\,T(n/2)+n\)

1. \(a=3\), \(b=2\), \(f(n)=n\).

2. \(n^{\log_b a}=n^{\log_2 3}\approx n^{1.585}\).

3. \(n^{1.585}\) è polinomialmente più grande di \(f(n)=n\) \(\longrightarrow\) caso 1.

4. \(f(n)=n=O\big(n^{\log_2 3-\epsilon}\big)\) con \(\epsilon=\log_2 3-1\approx 0.585>0\).

5. \(T(n)=\Theta\big(n^{\log_2 3}\big)\approx\Theta\big(n^{1.585}\big)\): l'algoritmo di Karatsuba è asintoticamente più veloce della moltiplicazione scolastica \(\Theta(n^2)\).

Esempio 16.8: Strassen: \(T(n)=7\,T(n/2)+n^2\)

1. \(a=7\), \(b=2\), \(f(n)=n^2\).

2. \(n^{\log_b a}=n^{\log_2 7}\approx n^{2.807}\).

3. \(n^{2.807}\) è polinomialmente più grande di \(f(n)=n^2\) \(\longrightarrow\) caso 1.

4. \(f(n)=n^2=O\big(n^{\log_2 7-\epsilon}\big)\) con \(\epsilon=\log_2 7-2\approx 0.807>0\).

5. \(T(n)=\Theta\big(n^{\log_2 7}\big)\approx\Theta\big(n^{2.807}\big)\), meglio del \(\Theta(n^3)\) della moltiplicazione di matrici standard (la cui ricorrenza divide et impera è \(T(n)=8T(n/2)+n^2\)).

Esempio 16.9: \(T(n)=2\,T(n/2)+n\log n\)

1. \(a=2\), \(b=2\), \(f(n)=n\log n\).

2. \(n^{\log_b a}=n^{\log_2 2}=n\).

3. \(f(n)=n\log n\) è più grande di \(n\), ma solo di un fattore \(\log n\), non polinomialmente \(\longrightarrow\) non è il caso 3; ha la forma \(n^{\log_b a}\log^k n\) \(\longrightarrow\) caso 2.

4. \(f(n)=n\log n=\Theta\big(n\log^k n\big)\) con \(k=1\).

5. \(T(n)=\Theta\big(n\log^{2} n\big)\).

Esempio 16.10: \(T(n)=3\,T(n/4)+n\log n\)

1. \(a=3\), \(b=4\), \(f(n)=n\log n\) (logaritmo in base 2).

2. \(n^{\log_b a}=n^{\log_4 3}\approx n^{0.792}\).

3. \(n^{0.792}\) è polinomialmente più piccolo di \(f(n)=n\log n\) \(\longrightarrow\) caso 3.

4. Poiché \(n\log n\ge n\) per \(n\ge 2\), abbiamo \(f(n)=\Omega\big(n^{\log_4 3+\epsilon}\big)\) con \(\epsilon=1-\log_4 3\approx 0.208\).
   Condizione di regolarità: per ogni \(n\ge 4\),

   \[ 3\, f\left(\frac{n}{4}\right) = 3\, \frac{n}{4}\,\log\frac{n}{4} \le \frac{3}{4}\, n\log n = c\, f(n) \qquad\text{con } c=\frac{3}{4}<1, \]

   perché \(\log(n/4)\le \log n\).

5. \(T(n)=\Theta(n\log n)\).

Esempio 16.11: \(T(n)=T(2n/3)+1\)

1. \(a=1\), \(b=\frac{3}{2}\) (infatti \(\frac{2n}{3}=\frac{n}{3/2}\)), \(f(n)=1\). Si noti che \(b\) non deve necessariamente essere un intero.

2. \(n^{\log_b a}=n^{\log_{3/2} 1}=n^0=1\).

3. \(1\) e \(f(n)=1\) hanno lo stesso ordine \(\longrightarrow\) caso 2.

4. \(f(n)=1=\Theta\big(n^{0}\log^k n\big)\) con \(k=0\).

5. \(T(n)=\Theta(\log n)\).

• Una verifica numerica. Per ciascuna delle ricorrenze precedenti con \(b\) intero abbiamo calcolato \(T(n)\) esattamente dalla ricorrenza, con \(T(1)=1\) e \(n=b^L\), e l'abbiamo divisa per l'ordine di grandezza \(g(n)\) dato dal teorema (logaritmi in base \(2\)). Il rapporto resta compreso tra due costanti positive, come garantisce il teorema, e si avvicina al limite indicato nell'ultima colonna.

Ricorrenza	\(g(n)\)	\(L=5\)	\(L=10\)	\(L=20\)	limite
\(16\,T(n/4)+n\)	\(n^2\)	1.3330	1.3333	1.3333	\(4/3\)
\(8\,T(n/2)+n^3\)	\(n^3\log n\)	1.2000	1.1000	1.0500	\(1\)
\(8\,T(n/3)+n^2\)	\(n^2\)	4.5606	6.5364	8.2414	\(9\)
\(T(n/2)+1\)	\(\log n\)	1.2000	1.1000	1.0500	\(1\)
\(2\,T(n/2)+n\)	\(n\log n\)	1.2000	1.1000	1.0500	\(1\)
\(2\,T(n/2)+1\)	\(n\)	1.9688	1.9990	2.0000	\(2\)
\(3\,T(n/2)+n\)	\(n^{\log_2 3}\)	2.7366	2.9653	2.9994	\(3\)
\(7\,T(n/2)+n^2\)	\(n^{\log_2 7}\)	2.2521	2.3284	2.3333	\(7/3\)
\(2\,T(n/2)+n\log n\)	\(n\log^2 n\)	0.6400	0.5600	0.5275	\(1/2\)
\(3\,T(n/4)+n\log n\)	\(n\log n\)	2.1933	2.8704	3.4020	\(4\)

• Per il merge sort, per esempio, \(T(2^{L})=2^{L}(L+1)\), quindi \(T(n)=n\log_2 n+n\) e \(\frac{T(n)}{n\log_2 n}=1+\frac{1}{L}\). Nel caso 3 la convergenza è lenta: il rapporto tende a \(\frac{1}{1-c}\) (\(9\) per \(c=\frac{8}{9}\), \(4\) per \(c=\frac{3}{4}\)), la limitazione che compare nella dimostrazione del teorema.

Il teorema dà l'ordine di grandezza, non la costante: nella tabella i rapporti tendono a costanti diverse, ma non crescono né svaniscono mai.

16.4 Quando il Master theorem non si applica

• Prima di applicare il teorema, si controlli sempre che valgano tutte le sue ipotesi. Ecco situazioni tipiche in cui il teorema non può essere applicato.

Esempio 16.12: Un vuoto tra il caso 1 e il caso 2: \(T(n)=2\,T(n/2)+n/\log_2 n\)

• \(a=2\), \(b=2\), \(f(n)=n/\log_2 n\), e \(n^{\log_b a}=n\).

• Non è il caso 1: \(f(n)\) è più piccola di \(n\), ma non polinomialmente più piccola. Per ogni \(\epsilon>0\)

  \[ \lim_{n\to\infty}\frac{n/\log_2 n}{n^{1-\epsilon}}=\lim_{n\to\infty}\frac{n^{\epsilon}}{\log_2 n}=+\infty, \]

  quindi \(f(n)\neq O(n^{1-\epsilon})\).

• Non è il caso 2: \(f(n)=n\log^{-1} n\) richiederebbe \(k=-1<0\).

• Non è il caso 3: \(f(n)\) è più piccola di \(n\).

• Soluzione con l'albero di ricorsione (Lemma 16.3), per \(n=2^L\) e \(T(1)=1\): il livello \(j\) costa

  \[ 2^j\,\frac{n/2^j}{\log_2(n/2^j)}=\frac{n}{L-j}, \qquad\text{quindi}\qquad T(n)=n+\sum_{j=0}^{L-1}\frac{n}{L-j}=n+n\sum_{i=1}^{L}\frac{1}{i}=n\,(1+H_L), \]

  dove \(H_L=\sum_{i=1}^{L}\frac1i\) è l'\(L\)-esimo numero armonico. Poiché \(\ln(L+1)\le H_L\le 1+\ln L\) (confronto con \(\int \frac{dx}{x}\)), \(H_L=\Theta(\log L)\) e

  \[ T(n)=\Theta(n\log\log n). \]

Esempio 16.13: Non in forma standard: \(T(n)=T(n-1)+n\)

• Il sottoproblema ha dimensione \(n-1\), non \(n/b\) con \(b>1\) costante: la ricorrenza non è in forma standard.

• Soluzione per iterazione (con \(T(1)=1\)):

  \[ T(n)=n+(n-1)+\dots+2+T(1)=\sum_{i=1}^{n} i=\frac{n(n+1)}{2}=\Theta(n^2). \]

Esempio 16.14: Sottoproblemi di dimensioni diverse: \(T(n)=T(n/3)+T(2n/3)+n\)

• I due sottoproblemi hanno dimensioni diverse \(n/3\) e \(2n/3\): la ricorrenza non è della forma \(a\,T(n/b)+f(n)\).

• Albero di ricorsione: ogni livello completo ha dimensione totale \(n\), quindi costo \(n\). Il cammino più corto dalla radice a una foglia (sempre \(n/3\)) ha lunghezza \(\log_3 n\), il più lungo (sempre \(2n/3\)) ha lunghezza \(\log_{3/2} n\). Pertanto i primi \(\log_3 n\) livelli sono completi (costo \(\ge n\log_3 n\)), e ci sono al più \(\log_{3/2} n+1\) livelli, ciascuno di costo al più \(n\). Quindi

  \[ T(n)=\Theta(n\log n). \]

Esempio 16.15: \(a\) non è costante: \(T(n)=2^n\,T(n/2)+n^n\)

• Il numero di sottoproblemi \(a=2^n\) dipende da \(n\): il Master theorem richiede che \(a\) sia una costante.

Esempio 16.16: \(a<1\): \(T(n)=0.5\,T(n/2)+1/n\)

• Qui \(a=0.5<1\): il teorema richiede \(a\ge 1\) (deve esserci almeno un sottoproblema).

Esempio 16.17: La condizione di regolarità non vale: \(T(n)=T(n/2)+n(2-\cos n)\)

• \(a=1\), \(b=2\), \(n^{\log_b a}=n^0=1\), \(f(n)=n(2-\cos n)\). Poiché \(1\le 2-\cos n\le 3\), abbiamo \(n\le f(n)\le 3n\), quindi

  \[ f(n)=\Theta(n)=\Omega\big(n^{0+\epsilon}\big)\quad\text{con }\epsilon=1: \]

  \(f(n)\) è polinomialmente più grande di \(n^{\log_b a}\), e ci aspetteremmo il caso 3.

• La condizione di regolarità non vale. Prendiamo \(n=2m\) pari. Allora

  \[ \frac{a\,f(n/2)}{f(n)}=\frac{m\,(2-\cos m)}{2m\,(2-\cos 2m)}=\frac{2-\cos m}{2\,(2-\cos 2m)}. \]

  Se \(\cos m\le -0.9\), allora \(2-\cos m\ge 2.9\) e \(\cos 2m=2\cos^2 m-1\ge 2\cdot 0.81-1=0.62\), quindi \(2(2-\cos 2m)\le 2.76\) e il rapporto è \(>1\). Poiché \(\pi\) è irrazionale, i valori \(m \bmod 2\pi\) (\(m\in\N\)) sono densi in \([0,2\pi)\), quindi esistono infiniti \(m\) con \(\cos m\le -0.9\) (per esempio \(m=3,9,16,22,28,\dots\)). Per \(m=22\): \(\cos 22\approx-0.99996\), \(\cos 44\approx 0.99984\), e il rapporto è \(\approx 1.4997\).
  Quindi non esiste alcuna costante \(c<1\) tale che \(a f(n/2)\le c f(n)\) per ogni \(n\) grande: il caso 3 non può essere applicato.

• Ciononostante la ricorrenza può essere risolta direttamente (con \(n/2\) che significa \(\lfloor n/2\rfloor\)): srotolandola,

  \[ n\le f(n)\le T(n)\le \sum_{j\ge 0} 3\,\frac{n}{2^j}+T(1)=6n+T(1), \qquad\text{quindi}\qquad T(n)=\Theta(n). \]

16.5 Dimostrazione del Master theorem

• Seguiamo la dimostrazione classica, che ha due parti:

  1. supponiamo prima che \(n\) sia una potenza esatta di \(b\), cioè \(n=b^L\) per qualche \(L\in\N\); allora tutte le dimensioni dei sottoproblemi \(n/b, n/b^2,\dots\) sono potenze esatte di \(b\) e non servono parti intere inferiori o superiori (Lemmi 16.3, Lemma 16.4 e Lemma 16.5);

  2. estendiamo poi il risultato a ogni numero naturale \(n\), quando \(n/b\) è \(\lceil n/b\rceil\) oppure \(\lfloor n/b\rfloor\) (Sezione 16.5.5).

16.5.1 Impostazione

• In tutta la dimostrazione poniamo

  \[ \blue{p=\log_b a}, \qquad\text{in modo che}\qquad b^p=a \quad\text{e}\quad p\ge 0 \ (\text{poiché } a\ge1). \]

• Per \(n\) potenza esatta di \(b\) consideriamo la ricorrenza

  \[\begin{equation*} \label{eq:recPowers} T(n)=\begin{cases} d & \text{se } n=1,\\ a\,T(n/b)+f(n) & \text{se } n=b^i,\ i\ge 1, \end{cases} \tag{16.1} \end{equation*}\]

  dove \(d>0\) è una costante (questo è il significato di \(T(1)=\Theta(1)\)).

• Supponiamo \(f(m)>0\) per ogni \(m\ge1\). Questo è sempre vero quando \(f\) conta i passi di un algoritmo; in generale, poiché \(f\) è asintoticamente positiva, solo un numero finito di valori è coinvolto e cambiano solo le costanti della dimostrazione.

• Le ipotesi dei tre casi valgono “per ogni \(n\) sufficientemente grande”, cioè per \(n\ge n_0\). La seguente osservazione ci permette di usarle per ogni potenza esatta di \(b\) almeno uguale a \(b\).

Osservazione 16.2: dalle potenze grandi a tutte le potenze

Siano \(f(m)>0\) e \(h(m)>0\) per ogni potenza esatta \(m\ge b\) di \(b\). Se esistono costanti \(c>0\) e \(n_0\) tali che \(f(m)\le c\,h(m)\) (risp. \(f(m)\ge c\,h(m)\)) per tutte le potenze esatte \(m\ge n_0\), allora esiste una costante \(c'>0\) tale che \(f(m)\le c'\,h(m)\) (risp. \(f(m)\ge c'\,h(m)\)) per tutte le potenze esatte \(m\ge b\) di \(b\).

Dimostrazione

Ci sono solo un numero finito di potenze esatte di \(b\) nell'intervallo \([b,n_0)\). Sia

\[ c'=\max\left\{c,\ \max_{b\le m<n_0}\frac{f(m)}{h(m)}\right\} \qquad\left(\text{risp. } c'=\min\left\{c,\ \min_{b\le m<n_0}\frac{f(m)}{h(m)}\right\}>0\right), \]

dove \(m\) varia tra le potenze esatte di \(b\). Allora \(f(m)\le c'h(m)\) (risp. \(\ge\)) sia per \(m<n_0\), per la scelta di \(c'\), sia per \(m\ge n_0\), poiché \(c\le c'\) (risp. \(c\ge c'\)). □

• La applicheremo con \(h(m)=m^{p-\epsilon}\) e \(h(m)=m^{p}\log_b^k m\), che sono positive per \(m\ge b\) (si noti che \(\log_b m\ge 1\) per \(m\ge b\)).

16.5.2 L'albero di ricorsione

Figura 16.1: Albero di ricorsione di \(T(n)=aT(n/b)+f(n)\) per \(n\) potenza esatta di \(b\). Ogni nodo interno ha \(a\) figli; il livello \(j\) ha \(a^j\) nodi, ciascuno un sottoproblema di dimensione \(n/b^j\) e costo \(f(n/b^j)\); le foglie sono a profondità \(\log_b n\).

• La radice (livello \(0\)) è un problema di dimensione \(n\); costa \(f(n)\) e genera \(a\) sottoproblemi di dimensione \(n/b\).

• Per induzione, il livello \(j\) contiene \(a^j\) nodi, ciascuno un sottoproblema di dimensione \(n/b^j\) e costo \(f(n/b^j)\): il costo totale del livello \(j\) è \(a^j f(n/b^j)\).

• La dimensione del sottoproblema raggiunge \(1\) quando \(n/b^j=1\), cioè a profondità \(j=\log_b n\): le foglie sono gli \(a^{\log_b n}\) nodi del livello \(\log_b n\), ciascuno di costo \(T(1)=d\).

Lemma 16.3: Costo dell'albero di ricorsione

Siano \(a\ge1\) e \(b>1\) costanti e sia \(f(n)>0\) per \(n\ge1\). Per ogni \(n\) potenza esatta di \(b\), la soluzione della ricorrenza \(\eqref{eq:recPowers}\) è

\[ T(n)=d\,n^{\log_b a}+\sum_{j=0}^{\log_b n-1}a^j f\left(\frac{n}{b^j}\right) =\Theta\big(n^{\log_b a}\big)+\sum_{j=0}^{\log_b n-1}a^j f\left(\frac{n}{b^j}\right). \]

Dimostrazione

Sia \(n=b^L\). Dimostriamo prima per induzione su \(i\in\{0,1,\dots,L\}\) che

\[\begin{equation*} \label{eq:unfold} T(n)=a^{i}\,T\left(\frac{n}{b^{i}}\right)+\sum_{j=0}^{i-1}a^j f\left(\frac{n}{b^j}\right). \tag{16.2} \end{equation*}\]

Per \(i=0\) la somma è vuota e \(\eqref{eq:unfold}\) diventa \(T(n)=T(n)\). Supponiamo che \(\eqref{eq:unfold}\) valga per qualche \(i<L\). Poiché \(n/b^{i}=b^{L-i}\) con \(L-i\ge1\), la ricorrenza dà \(T(n/b^{i})=a\,T(n/b^{i+1})+f(n/b^{i})\), quindi

\[ T(n)=a^{i}\Big(a\,T\big(\tfrac{n}{b^{i+1}}\big)+f\big(\tfrac{n}{b^{i}}\big)\Big)+\sum_{j=0}^{i-1}a^j f\big(\tfrac{n}{b^j}\big) =a^{i+1}\,T\big(\tfrac{n}{b^{i+1}}\big)+\sum_{j=0}^{i}a^j f\big(\tfrac{n}{b^j}\big), \]

che è \(\eqref{eq:unfold}\) per \(i+1\). Per \(i=L=\log_b n\) si ha \(T(n/b^L)=T(1)=d\), quindi

\[ T(n)=d\,a^{\log_b n}+\sum_{j=0}^{\log_b n-1}a^j f\left(\frac{n}{b^j}\right). \]

Resta da mostrare che \(a^{\log_b n}=n^{\log_b a}\). Scrivendo \(a=b^{\log_b a}\) e \(n=b^{\log_b n}\),

\[ a^{\log_b n}=\big(b^{\log_b a}\big)^{\log_b n}=b^{\log_b a\,\cdot\,\log_b n}=\big(b^{\log_b n}\big)^{\log_b a}=n^{\log_b a}. \]

Infine, \(d>0\) è una costante, quindi \(d\,n^{\log_b a}=\Theta(n^{\log_b a})\). □

• Il primo termine è il costo delle foglie: ci sono esattamente \(n^{\log_b a}\) foglie. La somma è il costo dei nodi interni (livelli \(0,\dots,\log_b n-1\)).

Esempio 16.18: Lemma 16.3 per \(T(n)=2T(n/2)+n\), \(T(1)=1\), \(n=8\)

Qui \(a=2\), \(b=2\), \(f(n)=n\), \(d=1\), \(\log_2 8=3\).

livello \(j\)	nodi \(a^j\)	dimensione \(n/b^j\)	costo per nodo	costo del livello
0	1	8	\(f(8)=8\)	8
1	2	4	\(f(4)=4\)	8
2	4	2	\(f(2)=2\)	8
3 (foglie)	\(8=8^{\log_2 2}\)	1	\(T(1)=1\)	8
			totale	32

Il Lemma 16.3 dà \(T(8)=1\cdot 8^{\log_2 2}+(8+8+8)=8+24=32\). Direttamente dalla ricorrenza:

\[ T(2)=2\cdot1+2=4,\qquad T(4)=2\cdot4+4=12,\qquad T(8)=2\cdot12+8=32. \quad\checkmark \]

16.5.3 Limitare la somma

• Per il Lemma 16.3, per risolvere la ricorrenza ci serve l'ordine di grandezza di

  \[ \blue{g(n)=\sum_{j=0}^{\log_b n-1}a^j f\left(\frac{n}{b^j}\right)}. \]

• Un'identità chiave, usata molte volte: poiché \(b^p=a\),

  \[\begin{equation*} \label{eq:keyIdentity} a^j\left(\frac{n}{b^j}\right)^{p}=\frac{a^j}{(b^{p})^j}\,n^{p}=\frac{a^j}{a^j}\,n^p=n^{p} \qquad\text{per ogni } j. \tag{16.3} \end{equation*}\]

• Nella somma, \(j\le \log_b n-1\), quindi le dimensioni \(m=n/b^j\) sono potenze esatte di \(b\) con \(m\ge b\): per l'Osservazione 16.2, le limitazioni su \(f\) dei casi 1 e 2 si possono usare per tutte.

Lemma 16.4: Limitazioni sulla somma

Siano \(a\ge1\) e \(b>1\) costanti, \(p=\log_b a\), sia \(f(m)>0\) per \(m\ge1\), e sia \(g(n)\) definita, per \(n\) potenza esatta di \(b\), come sopra. Allora:

1. se \(f(n)=O(n^{p-\epsilon})\) per qualche costante \(\epsilon>0\), allora \(g(n)=O(n^{p})\);

2. se \(f(n)=\Theta(n^{p}\log^k n)\) per qualche costante \(k\ge0\), allora \(g(n)=\Theta(n^{p}\log^{k+1} n)\);

3. se \(f(n)=\Omega(n^{p+\epsilon})\) per qualche costante \(\epsilon>0\), e \(a\,f(n/b)\le c\,f(n)\) per qualche costante \(c<1\) e per tutte le potenze esatte \(n\ge n_0\), allora \(g(n)=\Theta(f(n))\).

Dimostrazione (Dimostrazione del caso 1)

Per l'Osservazione 16.2 esiste una costante \(c>0\) tale che \(f(m)\le c\,m^{p-\epsilon}\) per ogni potenza esatta \(m\ge b\). Quindi, usando \(\eqref{eq:keyIdentity}\),

\[ g(n)\le c\sum_{j=0}^{\log_b n-1}a^j\left(\frac{n}{b^j}\right)^{p-\epsilon} = c\sum_{j=0}^{\log_b n-1}a^j\left(\frac{n}{b^j}\right)^{p}\left(\frac{b^j}{n}\right)^{\epsilon} = c\, n^{p-\epsilon}\sum_{j=0}^{\log_b n-1}\big(b^{\epsilon}\big)^j . \]

Questa è una serie geometrica finita di ragione \(b^\epsilon>1\) (poiché \(b>1\) e \(\epsilon>0\)):

\[ \sum_{j=0}^{\log_b n-1}\big(b^{\epsilon}\big)^j=\frac{(b^\epsilon)^{\log_b n}-1}{b^\epsilon-1} =\frac{(b^{\log_b n})^{\epsilon}-1}{b^\epsilon-1}=\frac{n^\epsilon-1}{b^\epsilon-1}. \]

Pertanto

\[ 0< g(n)\le c\, n^{p-\epsilon}\,\frac{n^\epsilon-1}{b^\epsilon-1}\le \frac{c}{b^\epsilon-1}\,n^{p}, \]

e poiché \(\frac{c}{b^\epsilon-1}\) è una costante positiva, \(g(n)=O(n^{p})\). □

Esempio 16.19: Caso 1 del Lemma 16.4: \(T(n)=16T(n/4)+n\), \(n=64\)

Qui \(p=\log_4 16=2\), \(f(m)=m=m^{2-1}\), quindi \(c=1\), \(\epsilon=1\). I livelli interni costano

\[ g(64)=1\cdot 64+16\cdot16+256\cdot 4=64+256+1024=1344: \]

i costi crescono del fattore \(b^\epsilon=4\) da un livello al successivo (sono dominati dai livelli più profondi). La formula della dimostrazione dà esattamente \(n^{p-\epsilon}\frac{n^\epsilon-1}{b^\epsilon-1}=64\cdot\frac{63}{3}=1344\), e la limitazione \(\frac{c}{b^\epsilon-1}n^p=\frac{4096}{3}\approx 1365.3\) vale. Aggiungendo le foglie, \(T(64)=4096+1344=5440\) con \(T(1)=1\).

Dimostrazione (Dimostrazione del caso 2)

Poiché \(\log^k n\) e \(\log_b^k n\) differiscono per un fattore costante, l'ipotesi è \(f(n)=\Theta(n^p\log_b^k n)\). Per l'Osservazione 16.2 esistono costanti \(c_1,c_2>0\) tali che

\[ c_1\,m^p\log_b^k m\le f(m)\le c_2\,m^p\log_b^k m\qquad\text{per ogni potenza esatta } m\ge b. \]

Sia \(L=\log_b n\). Per il termine \(j\) della somma, \(m=n/b^j\) e \(\log_b m=L-j\); per \(\eqref{eq:keyIdentity}\),

\[ a^j\left(\frac{n}{b^j}\right)^{p}\log_b^k\frac{n}{b^j}=n^p\,(L-j)^k . \]

Quindi, ponendo \(i=L-j\) (al variare di \(j\) da \(0\) a \(L-1\), \(i\) va da \(L\) a \(1\)),

\[ c_1\,n^p\, S_k(L)\ \le\ g(n)\ \le\ c_2\,n^p\, S_k(L), \qquad\text{dove}\quad S_k(L)=\sum_{i=1}^{L}i^k . \]

Dimostriamo ora che \(\big(\tfrac{L}{2}\big)^{k+1}\le S_k(L)\le L^{k+1}\), cioè \(S_k(L)=\Theta(L^{k+1})\).

• Limitazione superiore: ciascuno dei \(L\) termini soddisfa \(i^k\le L^k\) (poiché \(k\ge 0\)), quindi \(S_k(L)\le L\cdot L^k=L^{k+1}\).

• Limitazione inferiore: teniamo solo i termini con \(i\ge \lceil L/2\rceil\) (tutti i termini sono non negativi). Ce ne sono \(L-\lceil L/2\rceil+1\ge L/2\) e ciascuno è almeno \((L/2)^k\). Quindi \(S_k(L)\ge \frac{L}{2}\left(\frac{L}{2}\right)^k=\left(\frac{L}{2}\right)^{k+1}\).

Pertanto

\[ \frac{c_1}{2^{k+1}}\,n^p\log_b^{k+1}n\ \le\ g(n)\ \le\ c_2\,n^p\log_b^{k+1}n, \]

cioè \(g(n)=\Theta(n^p\log_b^{k+1}n)=\Theta(n^p\log^{k+1}n)\). □

Esempio 16.20: Caso 2 del Lemma 16.4: \(2T(n/2)+n\) e \(2T(n/2)+n\log_2 n\), \(n=16\)

Qui \(p=\log_2 2=1\) e \(L=\log_2 16=4\).

• \(f(n)=n\) (\(k=0\)): ogni livello costa \(2^j\cdot\frac{16}{2^j}=16=n^p\), quindi \(g(16)=4\cdot 16=64=n\,S_0(4)\), con \(S_0(4)=4=L\).

• \(f(n)=n\log_2 n\) (\(k=1\)): il livello \(j\) costa \(n^p(L-j)=16\,(4-j)\):

  \[ g(16)=64+48+32+16=160=16\,(4+3+2+1)=n\,S_1(4). \]

  Le limitazioni della dimostrazione danno \(\left(\frac{L}{2}\right)^{2}=4\le S_1(4)=10\le L^2=16\), quindi \(64\le g(16)\le 256\).

Dimostrazione (Dimostrazione del caso 3)

Limitazione inferiore. Tutti i termini di \(g(n)\) sono positivi e il termine \(j=0\) è \(f(n)\): quindi \(g(n)\ge f(n)\).

Limitazione superiore. Sia \(L=\log_b n\). Dimostriamo prima, per induzione su \(j\), che

\[\begin{equation*} \label{eq:regIter} a^j f\left(\frac{n}{b^j}\right)\le c^j f(n)\qquad\text{per ogni } j\ge 0 \text{ tale che } \frac{n}{b^{j-1}}\ge n_0 . \tag{16.4} \end{equation*}\]

Per \(j=0\) è un'uguaglianza. Sia \(j\ge1\) con \(n/b^{j-1}\ge n_0\). Allora anche \(n/b^{j-2}\ge n_0\), quindi l'ipotesi induttiva vale per \(j-1\); applicando la condizione di regolarità alla potenza esatta \(n/b^{j-1}\ge n_0\),

\[ a^j f\left(\frac{n}{b^j}\right)=a^{j-1}\left[a\, f\left(\frac{n/b^{j-1}}{b}\right)\right]\le a^{j-1}\,c\, f\left(\frac{n}{b^{j-1}}\right)\le c\cdot c^{j-1}f(n)=c^j f(n). \]

Dividiamo \(g(n)\) nei termini che soddisfano \(n/b^{j-1}\ge n_0\) (livelli alti) e negli altri (livelli bassi).

• Livelli alti: per \(\eqref{eq:regIter}\) e la serie geometrica infinita di ragione \(0<c<1\),

  \[ \sum_{\text{alti}}a^jf\left(\frac{n}{b^j}\right)\le f(n)\sum_{j=0}^{\infty}c^j=\frac{f(n)}{1-c}. \]

• Livelli bassi: se \(n/b^{j-1}<n_0\), allora \(m=n/b^j<n_0\) è una potenza esatta di \(b\) con \(m\ge b\), quindi \(f(m)\le M\), dove \(M\) è il massimo di \(f\) sulle (finite) potenze esatte di \(b\) in \([b,n_0)\). Inoltre \(a^j\le a^{L}=n^p\) (Lemma 16.3), e il numero di livelli bassi è al più \(h=\lceil\log_b n_0\rceil\) (corrispondono a \(m=b,b^2,\dots\) con \(m<n_0\)). Quindi

  \[ \sum_{\text{bassi}}a^jf\left(\frac{n}{b^j}\right)\le h\,M\,n^p . \]

Infine, \(f(n)=\Omega(n^{p+\epsilon})\) implica \(n^p=O(f(n))\) (infatti \(n^p\le n^{p+\epsilon}\)). Pertanto \(g(n)\le \frac{f(n)}{1-c}+hMn^p=O(f(n))\), e insieme alla limitazione inferiore \(g(n)=\Theta(f(n))\). □

Esempio 16.21: Caso 3 del Lemma 16.4: \(T(n)=8T(n/3)+n^2\), \(n=27\)

Qui \(p=\log_3 8\approx1.893\), \(c=\frac{8}{9}\) e la condizione di regolarità vale per ogni \(n\) (quindi \(n_0=1\), e non ci sono livelli bassi). Il livello \(j\) costa \(8^j\left(\frac{27}{3^j}\right)^2=729\left(\frac{8}{9}\right)^j\):

\[ g(27)=729+648+576=1953, \qquad f(27)=729\le g(27)\le\frac{f(27)}{1-8/9}=6561 . \]

I costi dei livelli decrescono geometricamente (sono dominati dalla radice). Con \(T(1)=1\): \(T(27)=8^{3}+1953=512+1953=2465\).

16.5.4 Dimostrazione per potenze esatte di \(b\)

Lemma 16.5: Master theorem per potenze esatte

I tre casi del Teorema 16.1 valgono per la ricorrenza \(\eqref{eq:recPowers}\), cioè quando \(n\) varia tra le potenze esatte di \(b\).

Dimostrazione

Per il Lemma 16.3, \(T(n)=\Theta(n^{p})+g(n)\), con \(g(n)>0\). Usiamo il Lemma 16.4.

• Caso 1: \(g(n)=O(n^p)\), quindi \(\Theta(n^p)\le T(n)\le \Theta(n^p)+O(n^p)\), cioè \(T(n)=\Theta(n^{p})=\Theta(n^{\log_b a})\).

• Caso 2: \(g(n)=\Theta(n^p\log^{k+1}n)\). Poiché \(n^p=O(n^p\log^{k+1}n)\), le foglie sono trascurabili: \(T(n)=\Theta(n^p\log^{k+1}n)=\Theta(n^{\log_b a}\log^{k+1}n)\).

• Caso 3: \(g(n)=\Theta(f(n))\). Poiché \(f(n)=\Omega(n^{p+\epsilon})\), abbiamo \(n^p=O(f(n))\), quindi di nuovo le foglie sono trascurabili: \(T(n)=\Theta(f(n))\).

□

16.5.5 Parti intere inferiori e superiori

• Consideriamo ora ogni numero naturale \(n\). Trattiamo in dettaglio la ricorrenza con le parti intere superiori,

  \[\begin{equation*} \label{eq:recCeil} T(n)=a\,T\big(\lceil n/b\rceil\big)+f(n)\quad\text{per } n\ge n', \qquad d_1\le T(n)\le d_2\quad\text{per } 1\le n<n', \tag{16.5} \end{equation*}\]

  dove \(n'\) e \(0<d_1\le d_2\) sono costanti, e \(f(n)>0\) per ogni \(n\ge1\). Nel caso 3 la condizione di regolarità si legge \(a\,f(\lceil n/b\rceil)\le c\,f(n)\) per ogni \(n\ge n_0\).

• Aumentare la soglia. I valori \(T(m)\) per \(1\le m<N\) sono un numero finito di numeri positivi per ogni costante \(N\ge n'\). Quindi, sostituendo \(d_1\) con il loro minimo e \(d_2\) con il loro massimo, possiamo supporre che la ricorrenza sia usata solo per \(n\ge N\), dove scegliamo

  \[ N\ge \max\left\{n',\ n_0,\ \frac{2b-1}{b-1}\right\}. \]

  Allora le ipotesi su \(f\) (e la condizione di regolarità) valgono per ogni argomento \(\ge N\).

• Dimensioni dei sottoproblemi. A profondità \(j\) dell'albero di ricorsione tutti i sottoproblemi hanno la stessa dimensione \(n_j\), dove

  \[ n_0^{*}=n,\qquad n_j=\big\lceil n_{j-1}/b\big\rceil\quad (j\ge1) \]

  (scriviamo \(n_0^{*}\) per la dimensione a profondità \(0\) per evitare confusione con la soglia \(n_0\)).

Lemma 16.6: Dimensioni con le parti intere superiori

Per ogni \(j\ge0\):

\[ \frac{n}{b^j}\ \le\ n_j\ <\ \frac{n}{b^j}+\frac{b}{b-1}. \]

Dimostrazione

Per induzione su \(j\). Per \(j=0\), \(n_0^*=n\). Per \(j\ge1\), usando \(x\le\lceil x\rceil<x+1\) e l'ipotesi induttiva,

\[\begin{gather*} n_j\ge \frac{n_{j-1}}{b}\ge\frac{n}{b^j},\\ n_j<\frac{n_{j-1}}{b}+1<\frac{1}{b}\left(\frac{n}{b^{j-1}}+\frac{b}{b-1}\right)+1=\frac{n}{b^j}+\frac{1}{b-1}+1=\frac{n}{b^j}+\frac{b}{b-1}. \qedhere \end{gather*}\]

□

Lemma 16.7: Master theorem con le parti intere superiori

I tre casi del Teorema 16.1 valgono per la ricorrenza \(\eqref{eq:recCeil}\), per ogni numero naturale \(n\).

Dimostrazione

Sia \(n\ge N\) e \(L=\log_b n\) (un numero reale, non necessariamente intero).

Passo 1: profondità dell'albero. Sia \(D\) il più piccolo \(j\) tale che \(n_j<N\) (la profondità alla quale la ricorsione si ferma). Per \(j\ge L\), il Lemma 16.6 dà \(n_j<1+\frac{b}{b-1}=\frac{2b-1}{b-1}\le N\); quindi \(D\le\lceil L\rceil<L+1\). Per \(j\le L-\log_b N\), \(n_j\ge n/b^j\ge N\); quindi \(D>L-\log_b N\). Dunque

\[ L-\log_b N< D< L+1 . \]

Passo 2: srotolamento. Esattamente come nella dimostrazione del Lemma 16.3 (la ricorrenza vale a ogni dimensione \(n_j\ge N\), cioè per \(j<D\)),

\[ T(n)=a^{D}\,T(n_D)+\sum_{j=0}^{D-1}a^j f(n_j). \]

Poiché \(d_1\le T(n_D)\le d_2\) e, per il Passo 1, \(\frac{n^p}{N^p}=a^{L-\log_b N}\le a^{D}\le a^{L+1}=a\,n^p\), il primo termine è \(\Theta(n^p)\).

Passo 3: limitazione di \(g(n)=\sum_{j=0}^{D-1}a^jf(n_j)\). Sia \(m_j=n/b^j\). Per \(0\le j\le D-1\) si ha \(j<L\), quindi \(m_j>1\), e per il Lemma 16.6

\[\begin{equation*} \label{eq:sandwichCeil} m_j\le n_j< m_j+\frac{b}{b-1}< C\,m_j,\qquad C=\frac{2b-1}{b-1}, \tag{16.6} \end{equation*}\]

mentre \(n_j\ge N\), quindi le limitazioni su \(f\) valgono in \(n_j\). Ricordiamo che \(a^jm_j^p=n^p\) per \(\eqref{eq:keyIdentity}\).

• Caso 1: \(f(n_j)\le c\,n_j^{p-\epsilon}\le c\,C'\,m_j^{p-\epsilon}\) con \(C'=\max\{1,C^{p-\epsilon}\}\) (se \(p-\epsilon\ge0\) si usa \(n_j<Cm_j\), altrimenti \(n_j\ge m_j\)). Come nel Lemma 16.4,

  \[ g(n)\le cC'n^{p-\epsilon}\sum_{j=0}^{D-1}(b^\epsilon)^j\le cC'n^{p-\epsilon}\frac{b^{\epsilon D}}{b^\epsilon-1}\le cC'n^{p-\epsilon}\frac{b^{\epsilon}n^{\epsilon}}{b^\epsilon-1}=O(n^p). \]

• Caso 2: Limitazione superiore: \(\log_b n_j<\log_b C+\log_b m_j\le\log_b C+L\), quindi

  \[ a^jf(n_j)\le c_2\,a^j\,C^pm_j^p\,(L+\log_b C)^k=c_2C^p\,n^p(L+\log_b C)^k, \]

  e sommando i \(D<L+1\) termini, \(g(n)\le c_2C^pn^p(L+1)(L+\log_bC)^k=O(n^p\log^{k+1}n)\).
  Limitazione inferiore: \(n_j\ge m_j>1\) dà \(a^jf(n_j)\ge c_1a^jm_j^p\log_b^km_j=c_1n^p(L-j)^k\). Per \(n\) abbastanza grande \(D-1\ge L/2\) (perché \(D>L-\log_bN\)), quindi tenendo solo i termini \(0\le j\le L/2\) (almeno \(L/2\) termini, ciascuno \(\ge (L/2)^k\)),

  \[ g(n)\ge c_1n^p\left(\frac{L}{2}\right)^{k+1}=\Omega(n^p\log^{k+1}n). \]

• Caso 3: \(g(n)\ge f(n)\) (termine \(j=0\)). Per \(1\le j\le D-1\) si ha \(n_{j-1}\ge N\ge n_0\), quindi la condizione di regolarità dà \(a\,f(n_j)=a\,f(\lceil n_{j-1}/b\rceil)\le c\,f(n_{j-1})\); per induzione (come in \(\eqref{eq:regIter}\)) \(a^jf(n_j)\le c^jf(n)\), quindi \(g(n)\le\frac{f(n)}{1-c}\) e \(g(n)=\Theta(f(n))\).

Passo 4: conclusione. \(T(n)=\Theta(n^p)+g(n)\) con le stesse limitazioni su \(g(n)\) del Lemma 16.4; i tre casi seguono esattamente come nella dimostrazione del Lemma 16.5. □

• Parti intere inferiori. Per \(T(n)=a\,T(\lfloor n/b\rfloor)+f(n)\) la dimostrazione è la stessa, con \(n_j=\lfloor n_{j-1}/b\rfloor\) e le limitazioni

  \[ \frac{n}{b^j}-\frac{b}{b-1}<n_j\le\frac{n}{b^j} \]

  (dimostrate come il Lemma 16.6, usando \(x-1<\lfloor x\rfloor\le x\)). Scegliendo anche \(N\ge\max\{b,\frac{2b}{b-1}\}\), per \(j<D\) si ottiene \(m_j\ge n_j\ge N\), quindi \(\frac{b}{b-1}\le\frac{m_j}{2}\) e \(\frac{m_j}{2}<n_j\le m_j\), che sostituisce \(\eqref{eq:sandwichCeil}\); inoltre \(L-\log_b\!\big(N+\frac{b}{b-1}\big)\le D\le L-\log_bN+1\). Cambiano solo le costanti.

• Questo completa la dimostrazione del Teorema 16.1. \(\blacksquare\)

Esempio 16.22: \(T(n)=T(\lceil n/2\rceil)+T(\lfloor n/2\rfloor)+n\), \(T(1)=1\)

Questa è l'esatta ricorrenza del merge sort su un array di lunghezza qualunque \(n\). Non ha la forma \(aT(\lceil n/b\rceil)+f(n)\), ma è compresa tra due ricorrenze di quella forma:

\[ U(n)=2\,U(\lceil n/2\rceil)+n,\qquad W(n)=2\,W(\lfloor n/2\rfloor)+n,\qquad U(1)=W(1)=1 . \]

• \(U\) e \(W\) sono non decrescenti (per induzione forte: se \(n<n''\) allora \(\lceil n/2\rceil\le\lceil n''/2\rceil\) e il termine aggiunto \(n\) è minore).

• Per induzione forte, \(W(n)\le T(n)\le U(n)\): per \(n\ge2\), usando che \(U\) è non decrescente e \(\lfloor n/2\rfloor\le\lceil n/2\rceil\),

  \[ T(n)\le U(\lceil n/2\rceil)+U(\lfloor n/2\rfloor)+n\le 2\,U(\lceil n/2\rceil)+n=U(n), \]

  e simmetricamente \(T(n)\ge 2\,W(\lfloor n/2\rfloor)+n=W(n)\).

• Per il Lemma 16.7 (caso 2, \(k=0\)) e la sua versione con le parti intere inferiori, \(U(n)=\Theta(n\log n)\) e \(W(n)=\Theta(n\log n)\). Quindi \(T(n)=\Theta(n\log n)\) per ogni \(n\), non solo per le potenze di 2.

Numericamente: \(T(1000)=10976\) e \(T(10^6)=20951424\), con \(\frac{T(n)}{n\log_2 n}\approx 1.101\) e \(\approx1.051\), rispettivamente.

16.5.6 La condizione di regolarità

• Nel caso 3 l'ipotesi \(f(n)=\Omega(n^{p+\epsilon})\) è in realtà implicata dalla condizione di regolarità (per \(f\) positiva). Questo spiega perché, in pratica, basta controllare la condizione di regolarità.

Osservazione 16.8: la regolarità implica la crescita polinomiale

Siano \(a\ge1\), \(b>1\), \(p=\log_b a\), e sia \(f(m)>0\) per ogni potenza esatta \(m\) di \(b\). Se \(a\,f(n/b)\le c\,f(n)\) per qualche costante \(0<c<1\) e per tutte le potenze esatte \(n\ge n_0\) di \(b\), allora

\[ f(n)=\Omega\big(n^{p+\epsilon}\big)\qquad\text{con}\qquad \epsilon=\log_b\frac{a}{c}-\log_b a=-\log_b c>0 . \]

Dimostrazione

Poiché \(0<c<1\), \(\epsilon=-\log_b c>0\) e \(\frac{a}{c}>a\ge 1\). La condizione di regolarità si può riscrivere come

\[ f(n)\ge\frac{a}{c}\,f\left(\frac{n}{b}\right)\qquad\text{per ogni potenza esatta } n\ge n_0 . \]

Sia \(n\ge n_0\) una potenza esatta di \(b\), e sia \(j\ge0\) il numero di volte in cui possiamo applicare questa disuguaglianza, cioè il più piccolo \(j\) tale che \(m=n/b^j\) soddisfa \(m<b\,n_0\) (quindi \(n_0\le m<b\,n_0\) quando \(n\ge n_0\); ogni dimensione intermedia \(n/b^i\), \(i<j\), è \(\ge b n_0 \ge n_0\)). Applicando la disuguaglianza \(j\) volte,

\[ f(n)\ge\left(\frac{a}{c}\right)^{j}f\left(\frac{n}{b^j}\right)\ge\left(\frac{a}{c}\right)^{j}\mu , \]

dove \(\mu>0\) è il minimo di \(f\) sulle (finite) potenze esatte di \(b\) in \([n_0,bn_0)\). Poiché \(b^j=n/m>\frac{n}{bn_0}\) e \(\frac{a}{c}=b^{\log_b(a/c)}\) con \(\log_b(a/c)>0\),

\[ \left(\frac{a}{c}\right)^{j}=\big(b^{j}\big)^{\log_b(a/c)}>\left(\frac{n}{bn_0}\right)^{\log_b(a/c)} . \]

Infine \(\log_b(a/c)=\log_b a-\log_b c=p+\epsilon\), quindi

\[ f(n)\ge \frac{\mu}{(bn_0)^{p+\epsilon}}\;n^{p+\epsilon}\qquad\text{per ogni potenza esatta } n\ge n_0, \]

cioè \(f(n)=\Omega(n^{p+\epsilon})\). □

• Per esempio, nell'Esempio 16.3 (\(8T(n/3)+n^2\), \(c=8/9\)) l'osservazione dà \(\epsilon=-\log_3\frac{8}{9}=2-\log_3 8\approx0.107\), esattamente il massimo \(\epsilon\) trovato lì.

• Il viceversa è falso: nell'Esempio 16.17, \(f(n)=\Omega(n^{p+1})\) ma la condizione di regolarità non vale.

16.6 Riepilogo

Come risolvere una ricorrenza \(T(n)\).

1. È in forma standard \(T(n)=a\,T(n/b)+f(n)\) con costanti \(a\ge1\), \(b>1\) e \(f(n)\) asintoticamente positiva?

   • No \(\longrightarrow\) si usi un altro metodo: iterazione, albero di ricorsione, sostituzione.

   • Sì \(\longrightarrow\) si calcoli \(n^{\log_b a}\) e lo si confronti con \(f(n)\).

2. \(f(n)=O(n^{\log_b a-\epsilon})\) per qualche \(\epsilon>0\) (polinomialmente più piccola)?
   \(\longrightarrow\) caso 1: \(\blue{T(n)=\Theta(n^{\log_b a})}\).

3. \(f(n)=\Theta(n^{\log_b a}\log^k n)\) per qualche \(k\ge0\)?
   \(\longrightarrow\) caso 2: \(\blue{T(n)=\Theta(n^{\log_b a}\log^{k+1}n)}\).

4. \(f(n)=\Omega(n^{\log_b a+\epsilon})\) per qualche \(\epsilon>0\) (polinomialmente più grande)? Si controlli la condizione di regolarità \(a\,f(n/b)\le c\,f(n)\) con \(c<1\):

   • vale \(\longrightarrow\) caso 3: \(\blue{T(n)=\Theta(f(n))}\);

   • non vale \(\longrightarrow\) il teorema non si applica.

5. Nessuno dei precedenti (un vuoto, per esempio \(f(n)=n^{\log_b a}/\log n\)) \(\longrightarrow\) il teorema non si applica: si usi l'albero di ricorsione \(T(n)=\Theta(n^{\log_b a})+\sum_{j=0}^{\log_b n-1}a^jf(n/b^j)\) (Lemma 16.3).

Base dei logaritmi: irrilevante in \(\log^k n\), essenziale in \(n^{\log_b a}\).

---

Esercizi su questo capitolo: Il Master theorem

Laboratorio interattivo

L'algoritmo del capitolo, un passo alla volta: muovi i cursori e premi ▶. Lo stesso grafico a tutta pagina, con gli altri del corso, è nel laboratorio interattivo.