Masters theorem (Algoritmo)

Il Master Theorem (o Teorema Principale) è uno strumento potente per risolvere ricorrenze del tipo . La chiave per applicare questo teorema è confrontare la funzione forzante con una funzione ausiliaria chiamata “funzione spartiacque”, definita come .

Il Master Theorem si articola in tre casi principali, ciascuno basato su questo confronto:

1. Caso 1: Se la funzione spartiacque cresce asintoticamente più velocemente di di almeno un fattore polinomiale, ovvero se per qualche costante , allora il costo totale è dominato dalla radice dell’albero di ricorsione. In questo caso, .

   • Esempio: Per la ricorrenza :
     • , .
     • La funzione spartiacque è .
     • La funzione forzante è .
     • Poiché per , rientriamo nel Caso 1.
     • Quindi, .

2. Caso 2: Se le due funzioni e hanno all’incirca lo stesso tasso di crescita, ovvero se per qualche costante , allora il costo totale è distribuito uniformemente su tutti i livelli dell’albero di ricorsione. In questo caso, .

   • Esempio: Per la ricorrenza :
     • , .
     • La funzione spartiacque è .
     • La funzione forzante è .
     • Poiché , rientriamo nel Caso 2 con .
     • Quindi, .

3. Caso 3: Se la funzione forzante cresce asintoticamente più velocemente di di almeno un fattore polinomiale, e soddisfa una condizione di regolarità ( per una costante ), allora il costo totale è dominato dalla funzione forzante stessa (cioè dalle operazioni non ricorsive). In questo caso, .

   • Esempio: Per la ricorrenza :
     • , .
     • La funzione spartiacque è .
     • La funzione forzante è .
     • Poiché per (ad esempio, , che è meno di 1, quindi cresce più velocemente), e verificando la condizione di regolarità: . Possiamo scegliere in modo che per sufficientemente grande.
     • Rientriamo nel Caso 3.
     • Quindi, .