El Teorema Maestro es una herramienta utilizada para resolver relaciones de recurrencia que surgen en el análisis de algoritmos de divide y vencerás. El Teorema Maestro proporciona una forma sistemática de resolver relaciones de recurrencia de la forma:

T(n) = aT(n/b) + f(n)

1. donde a, byf(n) son funciones positivas yn es el tamaño del problema. El Teorema Maestro proporciona condiciones para que la solución de la recurrencia tenga la forma O(n^k) para alguna constante k, y proporciona una fórmula para determinar el valor de k.
2. La versión avanzada del Teorema Maestro proporciona una forma más general del teorema que puede manejar relaciones de recurrencia que son más complejas que la forma básica. La versión avanzada del Teorema Maestro puede manejar recurrencias con múltiples términos y funciones más complejas.
3. Es importante señalar que el teorema maestro no es aplicable a todas las relaciones de recurrencia y es posible que no siempre proporcione una solución exacta para una recurrencia determinada. Sin embargo, es una herramienta útil para analizar la complejidad temporal de los algoritmos de divide y vencerás y proporciona un buen punto de partida para resolver recurrencias más complejas.

El teorema maestro se utiliza para determinar el tiempo de ejecución de algoritmos (algoritmos de divide y vencerás) en términos de notaciones asintóticas.
Considere un problema que se resuelve mediante recursividad.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

El algoritmo anterior divide el problema en a subproblemas, cada uno de tamaño n/b y resuélvalos recursivamente para calcular el problema y el trabajo adicional realizado para el problema viene dado por f(n), es decir, el tiempo para crear los subproblemas y combinar sus resultados en el procedimiento anterior.

Entonces, según el teorema maestro, el tiempo de ejecución del algoritmo anterior se puede expresar como:

 T(n) = aT(n/b) + f(n)>

donde n = tamaño del problema
a = número de subproblemas en la recursividad y a>= 1
n/b = tamaño de cada subproblema
f(n) = costo del trabajo realizado fuera de las llamadas recursivas, como dividir en subproblemas y costo de combinarlos para obtener la solución.

No todas las relaciones de recurrencia se pueden resolver con el uso del teorema maestro, es decir, si

• T(n) no es monótono, por ejemplo: T(n) = sin n
• f(n) no es un polinomio, por ejemplo: T(n) = 2T(n/2) + 2^norte

Este teorema es una versión avanzada del teorema maestro que se puede utilizar para determinar el tiempo de ejecución de los algoritmos de divide y vencerás si la recurrencia es de la siguiente forma:

donde n = tamaño del problema
a = número de subproblemas en la recursividad y a>= 1
n/b = tamaño de cada subproblema
b> 1, k>= 0 y p es un número real.

Entonces,

1. si a> b^k, entonces T(n) = θ(n^registro_ba)
2. si a = b^k, entonces
   (a) si p> -1, entonces T(n) = θ(n^registro_baregistro^p+1norte)
   (b) si p = -1, entonces T(n) = θ(n^registro_bainiciar sesión)
   (c) si p <-1, entonces T(n) = θ(n^registro_ba)
   
3. si un k, entonces
   (a) si p>= 0, entonces T(n) = θ(n^kregistro^pagnorte)
   (b) si p <0, entonces T(n) = θ(n^k)
   

Análisis de complejidad temporal –

Ejemplo 1: Búsqueda binaria – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 y p = 0
b^k= 1. Entonces, a = b^ky p> -1 [Caso 2.(a)]
T(norte) = θ(norte^registro_baregistro^p+1norte)
T(n) = θ(logn) Ejemplo 2: Ordenación por combinación – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Entonces, a = b^ky p> -1 [Caso 2.(a)]
T(norte) = θ(norte^registro_baregistro^p+1norte)
T(n) = θ(nlogn) Ejemplo 3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Entonces, un k y p = 0 [Caso 3.(a)]
T(norte) = θ(norte^kregistro^pagnorte)
T(norte) = θ(norte²)

Ejemplo 4: T(n) = 3T(n/2) + log²norte
a = 3, b = 2, k = 0, p = 2
b^k= 1. Entonces, a> b^k[Caso 1]
T(norte) = θ(norte^registro_ba)
T(norte) = θ(norte^registro₂3)

Ejemplo 5: T(n) = 2T(n/2) + nlog²norte
a = 2, b = 2, k = 1, p = 2
b^k= 2. Entonces, a = b^k[Caso 2.(a)]
T(norte) = θ(norte^registro_baregistro^p+1norte)
T(norte) = θ(norte^registro₂2registro³norte)
T(n) = θ(nlog³norte)

Ejemplo 6: T(n) = 2^norteT(norte/2) + norte^norte
Esta recurrencia no se puede resolver usando el método anterior ya que la función no tiene la forma T(n) = aT(n/b) + θ(n^kregistro^pagnorte)

Preguntas de práctica GATE –

• GATE-CS-2017 (Juego 2) | Pregunta 56
• PUERTA TI 2008 | Pregunta 42
• PUERTA CS 2009 | Pregunta 35

Aquí hay algunos puntos importantes a tener en cuenta con respecto al Teorema Maestro:

1. Recurrencias de divide y vencerás: El Teorema Maestro está diseñado específicamente para resolver relaciones de recurrencia que surgen en el análisis de algoritmos de divide y vencerás.
2. Forma de recurrencia: El teorema maestro se aplica a relaciones de recurrencia de la forma T(n) = aT(n/b) + f(n), donde a, b y f(n) son funciones positivas y n es el tamaño del problema.
3. Complejidad del tiempo: el teorema maestro proporciona condiciones para que la solución de la recurrencia tenga la forma de O(n^k) para alguna constante k, y proporciona una fórmula para determinar el valor de k.
4. Versión avanzada: la versión avanzada del Teorema maestro proporciona una forma más general del teorema que puede manejar relaciones de recurrencia que son más complejas que la forma básica.
5. Limitaciones: el teorema maestro no es aplicable a todas las relaciones de recurrencia y es posible que no siempre proporcione una solución exacta para una recurrencia determinada.
6. Herramienta útil: a pesar de sus limitaciones, el Teorema Maestro es una herramienta útil para analizar la complejidad temporal de los algoritmos de divide y vencerás y proporciona un buen punto de partida para resolver recurrencias más complejas.
7. Complementado con otras técnicas: en algunos casos, es posible que sea necesario complementar el teorema maestro con otras técnicas, como el método de sustitución o el método de iteración, para resolver completamente una relación de recurrencia determinada.