Teorema maestro
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
El Teorema Maestro es un método matemático que se usa para resolver ciertos casos particulares de ecuaciones de recurrencia como la siguiente: .
Consideremos una función t(n) que no sea decreciente:

con constantes a ≥ 1 y b ≥ 2. Obtenemos

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 [editar]

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

En esta a = 0.5 no cumple la condición a≥1.
Ejemplo de resolución [editar]
Veamos ahora un ejemplo de resolución de una recurrencia no lineal:

Utilizando el teorema maestro: 1. Obtenemos a=2, b=2,