En el análisis de algoritmos, el teorema maestro proporciona una cota superior asintótica para ecuaciones de recurrencia que ocurren en muchos algoritmos recursivos como en los divide y vencerás.
Fue popularizado por el libro Introducción a los algoritmos, en el cual fue tanto introducido como probado formalmente.
No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro, una generalización es el método Akra-Bazzi.
Considere un problema que puede ser resuelto a través de un algoritmo recursivo como el siguiente: Este algoritmo divide al problema original en subproblemas de forma recursiva, cada uno de estos subproblemas tienen tamaño n/b.
En este caso, cada nodo tendría un número a de hijos.
Cada nodo hará la cantidad de trabajo correspondiente al tamaño del subproblema
El trabajo total realizado por todas las llamadas del árbol es la suma de los trabajos hechos por cada uno de los nodos del árbol.
entonces: Como puede verse en la fórmula de arriba: Luego, vemos que se cumple la condición del caso 1: Luego por el teorema maestro tenemos que Si
Si es verdad que: Y si es verdad además que: Entonces: Como puede verse en la fórmula de arriba, las variables obtienen los siguientes valores: Luego se comprueba que satisface la condición del caso 3: La condición también se cumple: Entonces por el tercer caso del teorema maestro: Por consiguiente la relación de recurrencia T(n) es in Θ(n2).
Los siguientes casos no pueden ser resueltos a través de la utilización del teorema maestro:[2]