Master Theorem
El teorema maestro da la cota asintótica de la recurrencia divide y vencerás T(n)=aT(n/b)+f(n) en tres casos que comparan f con n^(log_b a).
Propósito
Analizar rápidamente la complejidad divide y vencerás sin expandir la recurrencia.
Mecanismo
Sea c=log_b a. Caso 1: f=O(n^(c-ε)) → T=Θ(n^c). Caso 2: f=Θ(n^c log^k n) → T=Θ(n^c log^(k+1) n). Caso 3: f=Ω(n^(c+ε)) más la condición de regularidad → T=Θ(f).
Casos de uso
- Análisis de complejidad
- Algoritmos divide y vencerás
- Resolución de recurrencias