Teorema Maestro

En el análisis de algoritmos, el teorema maestro proporciona una solución sencilla en términos asintóticos (usando una Cota superior asintótica) para ecuaciones de recurrencia que ocurren en muchos algoritmos recursivos tales como en el Algoritmo divide y vencerás. Fue popularizado por el libro Introducción a los algoritmos por Cormen, Leiserson, Rivest, y Stein, en el cual fue tanto introducido como probado formalmente. No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro.

Considere un problema que puede ser resuelto a través de un algoritmo recursivo como el siguiente:

En el algoritmo mostrado arriba se divide el problema original en una cantidad menor de subproblemas de manera recursiva, cada uno de estos subproblemas siendo del tamaño de n/b. Esto podría ser visualizado como la construcción de un árbol de llamadas al problema, siendo cada nodo del árbol una instancia recursiva del mismo y sus hijos siendo instancias de las llamadas subsiguientes. En el ejemplo de arriba, cada nodo tendría un número a de hijos. Cada nodo hará la cantidad de trabajo correspondiente al tamaño del subproblema n, pasado a esa instancia en particular, estando la cantidad de trabajo realizado determinado por ${displaystyle f(n)}$. 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.

Algoritmos como el descrito arriba pueden ser representados por una relación de recurrencia como la siguiente: ${displaystyle T(n)=a;Tleft({frac {n}{b}} ight)+f(n)}$. Esta relación de recurrencia puede ser sucesivamente sustituida en sí misma y expandida hasta obtener una expresión que represente la cantidad total de trabajo.^[1]​

El teorema maestro nos permite fácilmente calcular el tiempo de ejecución de este tipo de algoritmos recursivos en notación de Cota superior asintótica, sin la necesidad de hacer la expansión de las distintas llamadas recursivas.

El teorema maestro sirve para resolver relaciones recursivas de la siguiente forma:

En la aplicación de análisis de algoritmos recursivos, las constantes y funciones toman los siguientes significados:

Luego, es posible realizar una cota en notación Big O en los siguientes tres casos:

Si ${displaystyle f(n)=Oleft(n^{c} ight)}$ donde ${displaystyle c<log _{b}a}$ (usando Cota superior asintótica)

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 es verdad que para alguna constante k ≥ 0, que:

Entonces:

${displaystyle T(n)=2Tleft({frac {n}{2}} ight)+10n}$

Como podemos ver en la fórmula de arriba, las variables tienen los siguientes valores:

Luego, nos fijamos que cumpla la condición del caso 2:

Entonces por el segundo caso del teorema maestro:

Dando de esa manera que la relación de recurrencia de T(n) es Θ(n log n).

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 Θ(n²).

Los siguientes casos no pueden ser resueltos a través de la utilización del teorema maestro:^[2]​

---