¿Teorema maestro no aplicable?

Dada la siguiente ecuación recursiva

$$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ queremos aplicar el teorema de Master y observar que

$$n^{\log_2(2)} = n.$$

Ahora verificamos los dos primeros casos para $\varepsilon > 0$ , es decir si

• $n\log n \in O(n^{1-\varepsilon})$ o
• $n\log n \in \Theta(n)$ .

Los dos casos no están satisfechos. Entonces tenemos que verificar el tercer caso, es decir si

• $n\log n \in \Omega(n^{1+\varepsilon})$ .

Creo que la tercera condición tampoco se cumple. ¿Pero por qué? ¿Y cuál sería una buena explicación de por qué el teorema del Maestro no se puede aplicar en este caso?

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein (2ª edición, 2001) prueban los tres casos del Teorema maestro a los que se refiere en la Introducción a los algoritmos .

Se observa correctamente que la recurrencia en cuestión se encuentra entre el Caso 2 y el Caso 3. Es decir, crece más rápido que pero más lento que para cualquier .$f(n) = n \log n$$n$$n^{1+\varepsilon}$$\varepsilon > 0$

Sin embargo, el teorema puede generalizarse para cubrir esta recurrencia. Considerar

Caso 2A: Considere para algunos .$f(n) = \Theta (n^{\log_b a }\log_b^k n)$$k\geq 0$

Este caso se reduce al caso 2 cuando . Es intuitivamente claro que a lo largo de cada rama del árbol de recurrencia se agrega veces. Un bosquejo de una prueba más formal se puede encontrar a continuación. El resultado final es que$k = 0$$f(x)$$\Theta (\log_b n)$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$ .

En la Introducción a los algoritmos, esta afirmación se deja como un ejercicio.

Aplicando esta declaración a la recurrencia en cuestión, finalmente obtenemos

$$T(n) = \Theta(n \cdot \log^2 n).$$

Se pueden encontrar más detalles sobre el teorema maestro en la excelente (en mi humilde opinión) página de Wikipedia .

Como @sdcvvc señala en los comentarios para demostrar que el Caso 3 no se aplica aquí, se puede invocar la regla de L'Hospital que dice que para cualquier función y diferenciable en la vecindad de . Aplicando esto a y se puede demostrar que

$$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$$ $f(x)$$g(x)$$c$$f(n) = n \log n$$g(n) = n^{1+\varepsilon}$$\log n \not\in \Theta (n^{1+\varepsilon}).$

---

Boceto de la prueba del teorema maestro para el caso 2A.

Esta es una reproducción de partes de la prueba de Introducción a los algoritmos con las modificaciones necesarias .

Primero probamos el siguiente Lema.

Lema A:

Considere una función dondeEntonces

$$g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$$ $h(n) = n^{\log_b a} \log_b^k n.$$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Prueba: Sustituyendo en la expresión por se puede obtener $h(n)$$g(n)$

$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

Si es una potencia exacta de dada una recurrencia se puede reescribir como Sustituyendo con , moviendo afuera y aplicando Lemma A obtenemos$n$$b$

$$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$$ $$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j T(n/b^j).$$ $f(n)$$\Theta(n^{\log_b a} \log_b^k n)$$\Theta$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

Generalizar esto a un entero arbitrario que no es una potencia de está más allá del alcance de esta publicación.$n$$b$

El teorema de Akra-Bazzi es una generalización estricta del teorema maestro. Como beneficio adicional, su prueba es una tormenta de integrales que harán girar la cabeza ;-)

En cualquier caso, Sedgewick en su "Introducción al análisis de algoritmos" argumenta de manera convincente que uno debe esforzarse por probar asintóticos de tipo .$T(n) \sim g(n)$