Teorema principale

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, , e nel 1980, dove fu descritto come un metodo unificato per una famiglia di ricorrenze. Il nome di questo teorema è stato popolarizzato dal famoso manuale Introduzione agli algoritmi di Cormen, , Rivest e . 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 con e , in alcuni casi si può ottenere una soluzione confrontando con la funzione . Se è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale allora ; se le due funzioni hanno asintoticamente la stessa grandezza allora ; infine, se è sufficientemente regolare e polinomialmente più grande allora . Non sono coperti dal teorema i casi in cui sia asintoticamente più grande o più piccola di in modo non polinomiale.