Teorema dell'esperto

Il teorema dell'esperto, noto anche come teorema principale (in inglese master theorem) o teorema del maestro, è un teorema inerente all'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza. È stato inizialmente esposto da Jon Bentley, Dorothea Haken, e James B. Saxe nel 1980, dove fu descritto come un metodo unificato^[1] per una famiglia di ricorrenze.^[2] Il nome di questo teorema è stato popolarizzato dal famoso manuale Introduzione agli algoritmi di Cormen, Leiserson, Rivest e Stein. Non fornisce una soluzione a tutte le possibili relazioni di ricorrenza, ed una sua generalizzazione è il teorema di Akra-Bazzi.

Informalmente, il teorema afferma che, data una relazione di ricorrenza nella forma ${\displaystyle T(n)=aT\left({\frac {n}{b}}\right)+f(n)}$ con ${\displaystyle a\geq 1}$ e ${\displaystyle b>1}$, in alcuni casi si può ottenere una soluzione confrontando ${\displaystyle f}$ con la funzione ${\displaystyle n^{\log _{b}a}}$. Se ${\displaystyle f}$ è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale ${\displaystyle n^{\varepsilon }}$ allora ${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$; se le due funzioni hanno asintoticamente la stessa grandezza allora ${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log(n))=\Theta \left(f(n)\log(n)\right)}$; infine, se ${\displaystyle f}$ è sufficientemente regolare e polinomialmente più grande allora ${\displaystyle T(n)=\Theta \left(f(n)\right)}$. Non sono coperti dal teorema i casi in cui ${\displaystyle f}$ sia asintoticamente più grande o più piccola di ${\displaystyle n^{\log _{b}a}}$ in modo non polinomiale.^[3]