Prueba rigurosa de validez de la suposición

El teorema maestro es una herramienta hermosa para resolver ciertos tipos de recurrencias . Sin embargo, a menudo pasamos por alto una parte integral al aplicarlo. Por ejemplo, durante el análisis de Mergesort pasamos felizmente de

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

a

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considerando solo . Nos aseguramos de que este paso es válido, es decir, , porque comporta "bien". En general, suponemos que para el denominador común.$n=2^k$$T \in \Theta(T')$$T$$n=b^k$$b$

Es fácil construir recurrencias que no permiten esta simplificación usando vicioso . Por ejemplo, la recurrencia anterior para / con$f$$T\,$$\,T'$

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

producirá mediante el uso del teorema maestro de la manera habitual, pero hay claramente una subsecuencia que crece como \ Theta (n \ log n) . Vea aquí para otro ejemplo más artificial.$\Theta(n)$$\Theta(n \log n)$

¿Cómo podemos hacer esto "bien" riguroso? Estoy bastante seguro de que la monotonicidad es suficiente, pero ni siquiera la simple recurrencia de Mergesort es monótona; Hay un componente periódico (que se domina asintóticamente). ¿Es suficiente investigar $f$ , y cuáles son las condiciones necesarias y suficientes en $f$ que aseguran el funcionamiento del teorema maestro?

A lo largo de esta respuesta, suponemos y T no son negativos. Nuestra prueba funciona siempre que f = Θ ( g ) para algunos monótonos g . Esto incluye su ejemplo de Mergesort, en el que f = Θ ( n ) y cualquier función que tenga una tasa de crecimiento polinomial (o incluso Θ ( n a log b n ) ).$f$$T$$f = \Theta(g)$$g$$f=\Theta(n)$$\Theta(n^a \log^b n)$

Consideremos primero el caso de que es monótono no decreciente (relajaremos esta suposición más adelante). Nos concentramos en la recurrencia de su muestra T ( n ) = T ( ⌊ n / 2 ⌋ ) + T ( ⌈ n / 2 ⌉ ) + f ( n ) . Esta recurrencia necesita dos casos base, T ( 0 ) y T ( 1 ) . Suponemos que T ( 0 $f$

Afirmo que es monótono no decreciente. Probamos por inducción completa que T ( n + 1 ) ≥ T ( n ) . Esto se da para n = 0 , así que sea n ≥ 1 . Tenemos T ( n + 1 $T(n)$$T(n+1) \geq T(n)$$n = 0$$n \geq 1$ Esto implica que T(2⌊ log 2 n⌋)≤T(n)≤T(2⌈ log 2 n⌋). Entonces siT(

Ahora relajemos la suposición de que . Considere una nueva recurrencia T ' definida exactamente de la misma manera, solo T ′ ( 0 ) = T ′ ( 1 ) = min ( T ( 0 ) , T ( 1 ) ) . Podemos demostrar por inducción que T ′ ( n ) ≤ T ( n $T(0) \leq T(1)$$T'$$T'(0) = T'(1) = \min(T(0),T(1))$$T'(n) \leq T(n)$. Del mismo modo, podemos definir una nueva recurrencia satisfactoria T ″ ( 0 ) = T ″ ( 1 ) = max ( T ( 0 ) , T ( 1 ) ) , y luego T ( n ) ≤ T ″ ( n ) . Invocando el teorema del Maestro, vemos que T ′ = Θ ( h ) y T ″ = Θ $T''$$T''(0) = T''(1) = \max(T(0),T(1))$$T(n) \leq T''(n)$$T'=\Theta(h)$ para lamismafunción h , y entonces T = Θ ( h ) también.$T''=\Theta(h)$$h$$T = \Theta(h)$

Ahora relajemos la suposición de que es monótono. Suponga que f = Θ ( g ) para alguna función monótona g . Por lo tanto c g ( n ) ≤ f ( n ) ≤ C g ( n ) para algunos c , C > 0 y n suficientemente grande. Suponemos por simplicidad que n = 0 ; El caso general se puede manejar como en el párrafo anterior. Nuevamente definimos dos recurrencias T $f$$f = \Theta(g)$$g$$cg(n) \leq f(n) \leq Cg(n)$$c,C>0$$n$$n=0$ reemplazando f con c g , C g (respectivamente). Una vez más, el teorema del Maestro dará el mismo resultado (hasta múltiplos constantes), que también es idéntico (hasta múltiplos constantes) a lo que obtendríamos resolviendo la recurrencia original solo en potencias de dos.$T',T''$$f$$cg,Cg$