## 1.3.3 MÉTODO MAESTRO

Se aplica en casos como:

T(n) = 5 si n=0 y

9T(n/3) + n si n ≠ 0

Teorema: Sean a ≥ 1, b > 1 constantes, f(n) una función y T(n) una recurrencia definida sobre los enteros no negativos de la forma T(n) = aT(n/b) + f(n), donde n/b puede interpretarse como [n/b] o [n/b].

Entonces valen:
1. Si f(n) ∈ O(mlogba - ε ) para algún ε > 0 entonces T(n) ∈ Θ(nlogba).
2. Si f(n) ∈ Θ(nlogba) entonces T(n) ∈ Θ(nlogbalgn).
3. Si f(n) ∈ Ω(nlogba+ ε ) para algún ε > 0, y satisface af(n/b) ≤ cf(n) para alguna constante c < 1, entonces T(n) ∈ Θ(f(n)).

Ejemplos:
1. Si T(n)=9T(n/3)+n entonces a=9, b=3, se aplica el caso 1 con ε=1 y T(n) ∈ Θ(n2).
2. Si T(n)=T(2n/3)+1 entonces a=1, b=3/2, se aplica el caso 2 y T(n) = Θ(lgn).
3. Si T(n)=3T(n/4)+nlgn entonces a=3, b=4, f(n) ∈ Ω(nlog43 + 0.2) y 3(n/4) lg(n/4) ≤ 3/4n lg n, por lo que se aplica el caso 3 y T(n) ∈ Θ(nlgn).

###