Teorema mestre

Na análise de algoritmos, o teorema mestre para recorrências de divisão e conquista fornece uma análise assintótica (usando a notação Grande-O) para relações de recorrência que ocorrem na análise de muitos algoritmos de divisão e conquista. A abordagem foi apresentada pela primeira vez por Jon Bentley, Dorothea Haken, e James B. Saxe , em 1980, onde foi descrito como um "método unificador" para a solução de tais recorrências. O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado Algoritmos: teoria e prática por Cormen, Leiserson, Rivest e Stein. Nem todas as relações de recorrência podem ser resolvidas com o uso do teorema; suas generalizações incluem o método de Akra-Bazzi.