Metodo Master Theorem (algoritmi ricorsivi)

---

Index

1. Introduzione
2. Metodo
3. Esempi

---

Introduzione

Utilizzato per la risoluzione di equazione di ricorrenza di Algoritmi Iterativi basati sulla ricorrenza del dividi e impera

Equazione di ricorrenza

L’equazione di ricorrenza di questo tipo di algoritmi ha questa struttura:

$$T(n)=\{\begin{array}{ll}a\cdot T\left(\frac{n}{b}\right)+f(n)& \text{if }n>1\\ \Theta (1)& \end{array}$$

Dove $b>1$

• Il problema di dimensione $n$ è diviso in $a$ sotto problemi di dimensione $\frac{b}{n}$
• $f(n)$ è il costo della funzione escluse le chiamate ricorsive

---

Teorema

Un algoritmo del tipo:

$$T(n)=\{\begin{array}{ll}a\cdot T\left(\frac{n}{b}\right)+f(n)& \text{if }n>1\\ \Theta (1)& \end{array}$$

Ha 3 possibili soluzioni:

Caso 1

$$T(n)=\Theta (n^{{\log }_b(a)})\text{se}f(n)=O(n^{{\log }_b(a)-ϵ})$$

per un qualche $ϵ>0$

Caso 2

$$T(n)=\Theta (n^{{\log }_b(a)}\cdot \log n)\text{se}f(n)=\Theta (n^{{\log }_b(a)})$$

Caso 3

$$T(n)=\Theta (f(n))$$

Se:

• $f(n)=\Omega (n^{{\log }_b(a)+ϵ})$
• $a\cdot f\left(\frac{n}{b}\right)<c\cdot f(n)$

Sono entrambe vere per un qualche $ϵ>0$ e $0<c<1$

---

Esempi

---