AALIE

Teorema Maestro

Aplicabilidad, casos, regularidad y ejemplos resueltos del Teorema Maestro.

12. Teorema Maestro — Cuándo aplica

Existen diversos métodos para resolver ecuaciones de recurrencia, cada uno adecuado para diferentes tipos de problemas. Los métodos más utilizados son: el Método de Iteración (expandir la recurrencia algebraicamente), el Método del Árbol de Recursión (representación visual de niveles), el Método de Ecuación Característica (para recurrencias lineales homogéneas), las Suposiciones Inteligentes o Método de Sustitución (para verificar cotas mediante inducción) y el Teorema Maestro, que proporciona una solución directa para recurrencias divide y vencerás.

El Teorema Maestro es un método directo para resolver recurrencias divide y vencerás. Sirve cuando una recurrencia expresa un problema de tamaño $n$ como varios subproblemas del mismo tamaño reducido, más un costo externo de división, combinación o trabajo local.

Forma canónica

T (n) = a T (\frac{n}{b}) + f (n), a \geq 1, b > 1

En esta ecuación, $a$ indica cuántos subproblemas se generan, $b$ es el factor de reducción del tamaño, y $f (n)$ representa el costo de dividir el problema y combinar los resultados. El comportamiento asintótico dependerá de la comparación entre $f (n)$ y la función frontera $n^{l o g_{b} a}$ , usando un valor $ε$ para asegurar una diferencia polinómica clara.

Aplica cuando todos los llamados recursivos tienen el mismo tamaño $n / b$ .
Aplica cuando $a$ es constante y representa el número de subllamadas.
Aplica cuando $b > 1$ , es decir, el tamaño realmente se reduce por división.
Aplica cuando $f (n)$ es el costo no recursivo y puede compararse contra $n^{l o g_{b} a}$ .

No aplica

No aplica a formas de resta como $T (n) = T (n - 1) + f (n)$ . Eso es resta y vencerás, no divide y vencerás.
No aplica a formas como $T (n) = T (n /3) + T (2 n /3) + f (n)$ porque los subproblemas no tienen tamaño uniforme $n / b$ .
No aplica si $f (n)$ queda entre dos casos sin separación polinómica.
No entrega la función exacta $T (n)$ ; entrega el orden $Θ (\cdot)$ .

Paso a paso — Teorema Maestro

Detectar y validar la forma. Confirmar que la recurrencia es exactamente $T (n) = a T (n / b) + f (n)$ , con $a \geq 1$ y $b > 1$ .
Extraer parámetros. Identificar $a$ como número de llamadas, $b$ como factor de reducción y $f (n)$ como costo externo.
Calcular el exponente crítico. Calcular $p = lo g_{b} (a)$ y formar la frontera $n^{p}$ .
Comparar f(n) con n^p. Decidir si $f (n)$ está polinómicamente por debajo, igual o polinómicamente por encima de $n^{p}$ .
Verificar regularidad si parece caso 3. Probar $a f (n / b) \leq c f (n)$ para alguna constante $0 < c < 1$ .
Concluir o rechazar. Si uno de los casos aplica, concluir. Si ninguno aplica, usar otro método: normalmente árbol de recursión o sustitución.

Interpretación de p

$p = lo g_{b} (a)$ mide la presión de las hojas del árbol recursivo. Si $a$ es grande o $b$ reduce poco, aparecen muchas hojas y $n^{p}$ sube. Esa frontera compite contra el costo externo $f (n)$ .

Los tres casos del Teorema Maestro

Casos del Teorema Maestro

Caso	Condición	Interpretación	Resultado
Caso 1	$f (n) \in O (n^{p - ε})$ para algún $ε > 0$	$f (n)$ crece estrictamente más lento que $n^{p}$ . Dominan las hojas.	$T (n) = Θ (n^{p}) = Θ (n^{l o g_{b} a})$
Caso 2	$f (n) \in Θ (n^{p})$	$f (n)$ crece igual que $n^{p}$ . Cada nivel cuesta lo mismo.	$T (n) = Θ (n^{p} lo g n)$
Caso 3	$f (n) \in Ω (n^{p + ε})$ para algún $ε > 0$ , y $a f (n / b) \leq c f (n)$ con $0 < c < 1$	$f (n)$ crece estrictamente más rápido que $n^{p}$ . Domina la raíz.	$T (n) = Θ (f (n))$

No rompas el criterio de ε

En el caso 1 se compara contra $n^{p - ε}$ . En el caso 3 se compara contra $n^{p + ε}$ . Usar $p - ε$ en el caso 3 diría que basta crecer más que una función menor que $n^{p}$ , lo cual no garantiza que domine la raíz. Ese error destruye el Teorema Maestro.

$ε$ debe ser un número real positivo. No tiene que ser grande; basta con que exista. Por ejemplo, si $p = 2$ y $f (n) = n^{1.99}$ , el caso 1 aplica con $ε = 0.01$ . La separación no tiene que ser bonita, pero sí debe ser polinómica.

Regularidad solo se revisa en el caso 3

La condición $a f (n / b) \leq c f (n)$ exige que el costo total de los subproblemas sea estrictamente menor que una fracción constante del costo de la raíz. Debes encontrar una constante $c$ con $0 < c < 1$ . No basta decir 'parece que sí'.

Árbol de decisión del Teorema Maestro

Decisión de aplicabilidad y caso

Renderizando diagrama...

Ejemplos base

Ejemplo 1 — $T (n) = 2 T (n /2) + c n$ (Merge Sort / Quicksort mejor caso)

Parámetros

Identificamos los componentes de la recurrencia: dos subproblemas (a=2), división a la mitad (b=2) y costo lineal de combinación (f(n)=cn).

a = 2, b = 2, f (n) = c n

Exponente crítico

Calculamos el exponente crítico p usando el logaritmo de a en base b. Esto nos da la función frontera n^1.

p = lo g_{2} (2) = 1, n^{p} = n

Comparación

Comparamos el costo externo f(n) con la frontera n^p. En este caso, ambos crecen al mismo ritmo (lineal).

f (n) = c n \in Θ (n) = Θ (n^{p})

Caso

Dado que f(n) es del mismo orden que n^p, aplicamos el caso 2 del Teorema Maestro.

Caso 2

Resultado

El resultado final añade un factor logarítmico a la función frontera, resultando en una complejidad de n log n.

T (n) = Θ (n^{p} lo g n) = Θ (n lo g n)

Ejemplo 2 — $T (n) = 4 T (n /2) + n$

Parámetros

Extraemos los parámetros: hay 4 subllamadas, cada una reduce el tamaño a la mitad, y el costo externo es lineal.

a = 4, b = 2, f (n) = n

Exponente crítico

El exponente crítico p=2 define una frontera cuadrática n^2.

p = lo g_{2} (4) = 2, n^{p} = n^{2}

Comparación con separación

Comparamos f(n)=n con n^2. Como n es polinómicamente más pequeño que n^2, buscamos un epsilon que demuestre esta separación.

f (n) = n \in O (n^{2 - ε}) tomando ε = 1

Verificación

Verificamos que efectivamente n crece más lento que n^(2-1)=n^1.

n \in O (n^{1})

Caso

Al ser f(n) polinómicamente menor que la frontera, aplicamos el Caso 1.

Caso 1

Resultado

La complejidad total queda dominada por el trabajo en las hojas, que es de orden cuadrático.

T (n) = Θ (n^{2})

Ejemplo 3 — $T (n) = 4 T (n /2) + n^{3}$

Parámetros

Identificamos a=4, b=2 y un costo externo cúbico f(n)=n^3.

a = 4, b = 2, f (n) = n^{3}

Exponente crítico

La frontera sigue siendo n^2, pero ahora f(n) es n^3.

p = lo g_{2} (4) = 2, n^{p} = n^{2}

Comparación con separación

Observamos que n^3 crece polinómicamente más rápido que n^2. Usamos epsilon=1 para validarlo.

n^{3} \in Ω (n^{2 + ε}) tomando ε = 1

Intento de caso

Parece ser el Caso 3, pero este requiere obligatoriamente verificar la condición de regularidad.

Parece Caso 3, pero falta regularidad

Regularidad

Evaluamos la condición de regularidad: el costo de los subproblemas debe ser una fracción del costo original.

a f (n / b) = 4 (\frac{n}{2})^{3} = \frac{n ^{3}}{2}

Constante c

Encontramos c=1/2, que cumple con ser menor que 1. Se satisface la regularidad.

\frac{n ^{3}}{2} \leq \frac{1}{2} n^{3}, c = \frac{1}{2} < 1

Resultado

Al dominar el trabajo en la raíz (costo externo), la complejidad final es el orden de f(n), es decir, cúbico.

T (n) = Θ (f (n)) = Θ (n^{3})

Ejemplo 4 — $T (n) = 2 T (n /2) + \frac{n}{l o g n}$ (no aplica)

Parámetros

a = 2, b = 2, f (n) = \frac{n}{lo g n}

Exponente crítico

p = lo g_{2} (2) = 1, n^{p} = n

Caso 1

\frac{n}{lo g n} \in / O (n^{1 - ε}) para todo ε > 0

Razón

\frac{n / lo g n}{n ^{1 - ε}} = \frac{n ^{ε}}{lo g n} \to \infty

Caso 2

\frac{n}{lo g n} \in / Θ (n)

Caso 3

\frac{n}{lo g n} \in / Ω (n^{1 + ε})

Conclusión

El Teorema Maestro no aplica. Usar \overset{a}{ˊ} rbol de recursi \overset{o}{ˊ} n o sustituci \overset{o}{ˊ} n.

Ejemplo 5 — $T (n) = T (n /2) + 1$ (búsqueda binaria)

Parámetros

a = 1, b = 2, f (n) = 1

Exponente crítico

p = lo g_{2} (1) = 0, n^{p} = n^{0} = 1

Comparación

f (n) = 1 \in Θ (1) = Θ (n^{p})

Caso

Caso 2

Resultado

T (n) = Θ (1 \cdot lo g n) = Θ (lo g n)

Ejemplos enriquecidos y variantes típicas

Ejemplo enriquecido 1 — $T (n) = 8 T (n /2) + n^{2}$

Parámetros

a = 8, b = 2, f (n) = n^{2}

Exponente crítico

p = lo g_{2} (8) = 3

Comparación

n^{2} \in O (n^{3 - ε}) con ε = 1

Caso

Caso 1

Resultado

T (n) = Θ (n^{3})

Ejemplo enriquecido 2 — $T (n) = 3 T (n /3) + n$

Parámetros

a = 3, b = 3, f (n) = n

Exponente crítico

p = lo g_{3} (3) = 1

Comparación

f (n) = n \in Θ (n^{1})

Caso

Caso 2

Resultado

T (n) = Θ (n lo g n)

Ejemplo enriquecido 3 — $T (n) = T (n /2) + n$

Parámetros

a = 1, b = 2, f (n) = n

Exponente crítico

p = lo g_{2} (1) = 0, n^{p} = 1

Comparación

n \in Ω (n^{0 + ε}) con ε = 1

Regularidad

a f (n / b) = 1 \cdot \frac{n}{2} = \frac{n}{2} \leq \frac{1}{2} n

Caso

Caso 3

Resultado

T (n) = Θ (n)

Ejemplo enriquecido 4 — $T (n) = T (n /4) + n^{2}$

Parámetros

a = 1, b = 4, f (n) = n^{2}

Exponente crítico

p = lo g_{4} (1) = 0

Comparación

n^{2} \in Ω (n^{0 + ε}) por ejemplo con ε = 1

Regularidad

a f (n / b) = (\frac{n}{4})^{2} = \frac{n ^{2}}{16} \leq \frac{1}{16} n^{2}

Caso

Caso 3

Resultado

T (n) = Θ (n^{2})

Ejemplo enriquecido 5 — $T (n) = 9 T (n /3) + n^{2} lo g^{5} n$

Límite del Teorema Maestro básico

Con el Teorema Maestro básico de tres casos, este ejemplo no encaja en caso 1, 2 ni 3: $n^{2} lo g^{5} n$ es mayor que $n^{2}$ , pero no es polinómicamente mayor que $n^{2}$ . Requiere una versión extendida del Teorema Maestro o método alterno.

Parámetros

a = 9, b = 3, f (n) = n^{2} lo g^{5} n

Exponente crítico

p = lo g_{3} (9) = 2, n^{p} = n^{2}

No caso 2 básico

n^{2} lo g^{5} n \in / Θ (n^{2})

No caso 3 básico

n^{2} lo g^{5} n \in / Ω (n^{2 + ε}) para ning \overset{u}{ˊ} n ε > 0

Conclusión básica

Teorema Maestro b \overset{a}{ˊ} sico: no aplica

Resultado por versión extendida

T (n) = Θ (n^{2} lo g^{6} n)

Errores típicos

Errores frecuentes al aplicar el Teorema Maestro

Error	Por qué está mal	Corrección
Aplicarlo a $T (n) = T (n - 1) + f (n)$	Eso no divide el tamaño entre $b$ . Es resta, no división.	Usar iteración o ecuación característica, según corresponda.
Confundir $a$ con $b$	$a$ cuenta llamados; $b$ reduce tamaño.	Leer primero el número de términos $T (\cdot)$ y luego el denominador del argumento.
Usar $n^{p - ε}$ en el caso 3	El caso 3 exige que $f (n)$ sea polinómicamente mayor que $n^{p}$ .	Usar $n^{p + ε}$ en el caso 3.
Omitir regularidad en el caso 3	Sin regularidad, el caso 3 no está demostrado.	Calcular $a f (n / b)$ y encontrar $c < 1$ .
Decir que el resultado es la función exacta	El teorema solo entrega orden asintótico.	Reportar $Θ (\cdot)$ , no una fórmula exacta completa.
Forzar un caso cuando $f (n)$ cae entre casos	Algunas funciones no tienen separación polinómica suficiente.	Declarar no aplicable y usar árbol o sustitución.

Resumen operativo

Receta mínima

Validar forma $T (n) = a T (n / b) + f (n)$ .
Extraer $a$ , $b$ y $f (n)$ .
Calcular $p = lo g_{b} (a)$ .
Comparar $f (n)$ contra $n^{p}$ .
Caso 1: si $f (n) \in O (n^{p - ε})$ , entonces $T (n) = Θ (n^{p})$ .
Caso 2: si $f (n) \in Θ (n^{p})$ , entonces $T (n) = Θ (n^{p} lo g n)$ .
Caso 3: si $f (n) \in Ω (n^{p + ε})$ y hay regularidad, entonces $T (n) = Θ (f (n))$ .

12. Teorema Maestro — Cuándo aplica

Forma canónica

Paso a paso — Teorema Maestro

Los tres casos del Teorema Maestro

Casos del Teorema Maestro

Árbol de decisión del Teorema Maestro

Decisión de aplicabilidad y caso

Ejemplos base

Ejemplo 1 — T(n)=2T(n/2)+cn (Merge Sort / Quicksort mejor caso)

Ejemplo 2 — T(n)=4T(n/2)+n

Ejemplo 3 — T(n)=4T(n/2)+n3

Ejemplo 4 — T(n)=2T(n/2)+lognn​ (no aplica)

Ejemplo 5 — T(n)=T(n/2)+1 (búsqueda binaria)

Ejemplos enriquecidos y variantes típicas

Ejemplo enriquecido 1 — T(n)=8T(n/2)+n2

Ejemplo enriquecido 2 — T(n)=3T(n/3)+n

Ejemplo enriquecido 3 — T(n)=T(n/2)+n

Ejemplo enriquecido 4 — T(n)=T(n/4)+n2

Ejemplo enriquecido 5 — T(n)=9T(n/3)+n2log5n

Errores típicos

Errores frecuentes al aplicar el Teorema Maestro

Resumen operativo

Ejemplo 1 — $T (n) = 2 T (n /2) + c n$ (Merge Sort / Quicksort mejor caso)

Ejemplo 2 — $T (n) = 4 T (n /2) + n$

Ejemplo 3 — $T (n) = 4 T (n /2) + n^{3}$

Ejemplo 4 — $T (n) = 2 T (n /2) + \frac{n}{l o g n}$ (no aplica)

Ejemplo 5 — $T (n) = T (n /2) + 1$ (búsqueda binaria)

Ejemplo enriquecido 1 — $T (n) = 8 T (n /2) + n^{2}$

Ejemplo enriquecido 2 — $T (n) = 3 T (n /3) + n$

Ejemplo enriquecido 3 — $T (n) = T (n /2) + n$

Ejemplo enriquecido 4 — $T (n) = T (n /4) + n^{2}$

Ejemplo enriquecido 5 — $T (n) = 9 T (n /3) + n^{2} lo g^{5} n$