Teorema maestro

El Teorema maestro es un método matemático que se usa para resolver ciertos casos particulares de ecuaciones de recurrencia como la siguiente: $t(n) = t(\tfrac{n}{2}) + 1$.

Consideremos una función t(n) que no sea decreciente:

$t(n)=\begin{cases}at\left(\frac{n}{b}\right)+f(n)&n>1\\ \theta(1)&n=1\end{cases}$

con constantes a ≥ 1 y b ≥ 2. Obtenemos $d=log_b a \,$

$t(n)= \begin{cases} \theta(n^d)&\mbox{Si }\exist\varepsilon>0\mbox{ tal que }f(n)\in O(n^{d-\varepsilon})\\ \theta(n^d \log^{k+1}(n))&\mbox{Si }f(n)\in \theta(n^d \log^{k}(n))\\ \theta(f(n))&\mbox{Si }\exist\varepsilon>0\mbox{ tal que }f(n)\in\Omega(n^{d+\varepsilon})\mbox{ y}\\ &\exist\delta<1\mbox{ tal que }\forall n\geq n_0\mbox{ se cumple }af\left(\frac{n}{b}\right)\leq ef(n) \end{cases}$

Nota: θ(orden exacto), O (orden superior), Ω(orden inferior), según la notación de Landau.

Ejemplos de casos no válidos para el Teorema maestro

$T(n) = 2^nT\left (\frac{n}{2}\right )+n^n$

Esta no es válida porque a = 2ⁿ no es constante.

$T(n) = 0.5T\left (\frac{n}{2}\right )+n$

En esta a = 0.5 no cumple la condición a≥1.

Ejemplo de resolución

Veamos ahora un ejemplo de resolución de una recurrencia no lineal:

$t(n) = 2\cdot t(\tfrac {n}{2})$

Utilizando el teorema maestro:

1. Obtenemos a=2, b=2, d = log₂2 =1 y f (n) = 0.
2. Probamos la primera sentencia del teorema maestro:

¿Existe ε > 0 tal que f (n) ∈ O[orden superior](n^(d - ε))? Se ve claramente que n^(d - ε) para ε > 0 es 0 igual que f (n).

Ya sabemos que la solución del orden exacto de n^d = n¹ = n.

Ahora vamos a ver que ninguna de las otras sentencias puede ser verdadera:

• La 2ª sentencia no puede ser porque no existe ningún valor de k para el cual (n^d·log^kn)=0
• La 3ª sentencia no puede ser porque n^(d + ε) para d = 1, ya es mayor que 0.

Ahora resolvamos la recurrencia (el resultado debe ser de orden n, como ya hemos calculado):

t (n) = 2·t(n/2)

m = log₂2

2^m = n

>>1.Sustituimos n en la ecuación recurrente:

t(2^m) = 2·t(2^m/2)

-> t(2^m) = 2·t(2^{m − 1})

s (m) = t(2^m)

>>2.Sustituimos t(2^m) por s (m) y t(2^{m − 1}) por s (m-1)

s (m) = 2·s (m-1)

>>Resolvemos esta ecuación recurrente

r - 2 = 0 -> r = 2

s (m) = z·2^m

>>Deshacemos el cambio 2:

t(2^m) = 2·(z·2^{m − 1})

-> t(2^m) = z·2^m

>>Deshacemos el cambio 1:

t (n) = z·n

Nota: z la calcularíamos con el caso base de la recurrencia inicial.

Observamos que t (n) = z·n es de orden n tal como habíamos calculado con el teorema maestro.

Véase también

• Ecuación recurrente