Divisão e conquista e o Teorema Mestre

Algoritmos de divisão e conquista quebram o problema em a subproblemas de tamanho n/b e gastam f(n) para dividir e combinar:

T(n) = a·T(n/b) + f(n)

O Teorema Mestre compara f(n) com n^(log_b a), o custo total das folhas da árvore de recursão:

Caso 1: f(n) = O(n^(log_b a − ε))      ⇒ T(n) = Θ(n^(log_b a))         folhas dominam
Caso 2: f(n) = Θ(n^(log_b a))          ⇒ T(n) = Θ(n^(log_b a) · log n)   equilíbrio
Caso 3: f(n) = Ω(n^(log_b a + ε))      ⇒ T(n) = Θ(f(n))                raiz domina*

* se também a·f(n/b) ≤ c·f(n) para algum c < 1

Exemplos clássicos

Busca binária:   T(n) = T(n/2) + 1     a=1, b=2, n⁰=1 → caso 2 → Θ(log n)
Merge sort:      T(n) = 2T(n/2) + n    a=2, b=2, n¹=n → caso 2 → Θ(n log n)
Karatsuba:       T(n) = 3T(n/2) + n    n^1,585       → caso 1 → Θ(n^1,585)
Strassen:        T(n) = 7T(n/2) + n²   n^2,807       → caso 1 → Θ(n^2,807)

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    m = max(len(str(x)), len(str(y))) // 2
    a, b = divmod(x, 10**m)
    c, d = divmod(y, 10**m)
    ac, bd = karatsuba(a, c), karatsuba(b, d)
    meio = karatsuba(a + b, c + d) - ac - bd   # 3 multiplicações, não 4
    return ac * 10**(2*m) + meio * 10**m + bd