# Teorema mestre (análise de algoritmos)

Na análise de algoritmos, o teorema mestre para recorrências de divisão e conquista fornece uma análise assintótica (usando a notação Grande-O) para relações de recorrência que ocorrem na análise de muitos algoritmos de divisão e conquista. A abordagem foi apresentada pela primeira vez por Jon Bentley, Dorothea Haken, e James B. Saxe , em 1980, onde foi descrito como um "método unificador" para a solução de tais recorrências. O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado Algoritmos: teoria e prática por Cormen, Leiserson, Rivest e Stein.
Nem todas as relações de recorrência podem ser resolvidas com o uso do teorema; suas generalizações incluem o método de Akra-Bazzi.

## Introdução

Considere um problema que pode ser resolvido usando um algoritmo recursivo como o algoritmo a seguir:
O algoritmo acima divide o problema em um número de subproblemas recursivamente, cada subproblema sendo de tamanho n/b. A sua árvore de chamadas tem um nó para cada chamada recursiva, com os filhos do nó sendo as outras chamadas feitas a partir dessa chamada. As folhas da árvore são os casos base da recursão, os subproblemas (de tamanho menor do que k) que não se resolve recursivamente. O exemplo acima teria $a$ nós-filhos em cada nó que não fosse uma folha. Cada nó realiza uma quantidade de trabalho que corresponde ao tamanho do sub problema n passado para essa instância da chamada recursiva e dada por $f(n)$. A quantidade total de trabalho realizado pelo algoritmo completo é a soma do trabalho realizado por todos os nós na árvore.$$$$$$O tempo de execução de um algoritmo, como o 'p' acima em uma entrada de tamanho 'n', geralmente denotado por $T(n)$, pode ser expresso pela relação de recorrência
$T(n)=aT({\frac {n}{b}})+f(n)$
onde $f(n)$ é o tempo para criar os subproblemas e combinar seus resultados no procedimento acima. Essa equação pode ser substituída, sucessivamente, por si mesma e se expandir para obter uma expressão para a quantidade total de trabalho realizado. O teorema mestre permite que muitas relações de recorrência desta forma serem convertidas para notação teta diretamente, sem fazer uma expansão da relação recursiva.$$

## Forma genérica

$$$$$$$$O teorema mestre às vezes produz limites assintoticamente rígidos para algumas recorrências de algoritmos de divisão e conquista,que dividem uma entrada em subproblemas menores de tamanhos iguais, resolvem os subproblemas recursivamente e combinam as soluções dos subproblemas para fornecer uma solução para o problema original. O tempo para tal algoritmo pode ser expresso adicionando o tempo de execução no nível superior de sua recursão (para dividir os problemas em subproblemas e depois combinar as soluções de subproblemas) junto com o tempo de execução nas chamadas recursivas do algoritmo. Se denota o tempo total para o algoritmo em uma entrada de tamanho e indica a quantidade de tempo gasto no nível superior da recorrência, então o tempo pode ser expresso por uma relação de recorrência que assume a forma:
$T(n)=aT({\frac {n}{b}})+f(n)$$$$$$$$$$$$$Aqui $n$ é o tamanho da entrada de um problema, $a$ é o número de subproblemas na recursão, e $b$ é o fator pelo qual o tamanho do subproblema é reduzido em cada chamada recursiva (por exemplo, se o valor for 2, então o subproblema terá metade do tamanho). O teorema abaixo também assume um caso base para a recorrência, $T(n)=\Theta (1)$ quando $n$ é menor que algum limite $\kappa >0$.
Recorrências desta forma frequentemente satisfazem um dos três casos a seguir, baseado em como o trabalho para dividir/recombinar o problema $f(n)$ relaciona-se com a expoente crítico. (A tabela abaixo utiliza o padrão de big O notation.)$$$$
    $c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblemas}})/\log({\text{tamanho relativo do subproblema}})$
| Caso | Descrição | Condição sobre $f(n)$ em relação a $c_{\operatorname {crit} }$, i.e. $\log _{b}a$ | Limite do Teorema Mestre | Exemplos notacionais |
| 1 | O trabalho para dividir/recombinar um problema é reduzido pelos subproblemas. i.e. a árvore de recursão é leaf-heavy | Quando $f(n)=O(n^{c})$ onde $c<c_{\operatorname {crit} }$ (limitado superiormente por um polinômio de expoente menor) | ... então $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (O termo de divisão não aparece; a estrutura da árvore recursiva domina.) | Se $b=a^{2}$ and $f(n)=O(n^{1/2-\epsilon })$, então $T(n)=\Theta (n^{1/2})$. |
| 2 | O trabalho para dividir/recombinar um problema é comparável aos subproblemas. | Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k\geq 0$ (faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional $\log$s) | ... então $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (O limite é o termo de divisão, em que o log é aumentado por uma única potência.) | Se $b=a^{2}$ e $f(n)=\Theta (n^{1/2})$, então $T(n)=\Theta (n^{1/2}\log n)$. Se $b=a^{2}$ e $f(n)=\Theta (n^{1/2}\log n)$, então $T(n)=\Theta (n^{1/2}\log ^{2}n)$. |
| 3 | O trabalho para dividir/recombinar um problema domina os subproblemas. i.e. a árvore de recursão é root-heavy. | Quando $f(n)=\Omega (n^{c})$onde $c>c_{\operatorname {crit} }$ (limitado inferiormente por um polinômio de maior expoente) | ... isso não produz necessariamente nada. Se é sabido ainda que $af\left({\frac {n}{b}}\right)\leq kf(n)$ para alguma constante $k<1$ e suficientemente grande $n$ (frequentemente chamado de condição de regularidade) então o total é dominado pelo termo de divisão $f(n)$: $T\left(n\right)=\Theta \left(f(n)\right)$ | Se $b=a^{2}$ e $f(n)=\Omega (n^{1/2+\epsilon })$ e a condição de regularidade é satisfeita, então $T(n)=\Theta (f(n))$. |
Uma extensão útil do caso 2 abrange todos os valores de $k$
| Caso | $f(n)$ $c_{\operatorname {crit} }$, i.e. $\log _{b}a$ | Limite do teorema mestre | Exemplos notacionais |
| 2a | Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k>-1$ | ... então$T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log ^{k+1}n\right)$ (O limite é o termo de divisão, em que o log é aumentado por uma única potência.) | $b=a^{2}$ e$f(n)=\Theta (n^{1/2}/\log ^{1/2}n)$, então$T(n)=\Theta (n^{1/2}\log ^{1/2}n)$. |
| 2b | Quando $f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ fpara $k=-1$ | ... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\log \log n\right)$ (O limite é o termo de divisão, em que o log recíproco é substituído por um log iterado.) | Se $b=a^{2}$ $f(n)=\Theta (n^{1/2}/\log n)$, então $T(n)=\Theta (n^{1/2}\log \log n)$. |
| 2c | Quando$f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)$ para qualquer $k<-1$ | ... then $T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)$ (O limite é o termo de divisão, onde o log desaparece.) | Se $b=a^{2}$ e$f(n)=\Theta (n^{1/2}/\log ^{2}n)$, então $T(n)=\Theta (n^{1/2})$. |

### Exemplos
#### Exemplo do caso 1

    $T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$
Como se pode ver a partir da fórmula acima:
    $a=8,\,b=2,\,f(n)=1000n^{2}$, então
    $f(n)=O\left(n^{c}\right)$, onde $c=2$
Em seguida, vamos ver se conseguimos satisfazer a condição do caso 1:
    $\log _{b}a=\log _{2}8=3>c$.
Do primeiro caso do teorema mestre, segue que
    $T(n)=\Theta \left(n^{\log _{b}a}\right)=\Theta \left(n^{3}\right)$
(de fato, a solução exata da relação de recorrência é $T(n)=1001n^{3}-1000n^{2}$, assumindo $T(1)=1$).

#### Exemplo do caso 2

$T(n)=2T\left({\frac {n}{2}}\right)+10n$
Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:
    $a=2,\,b=2,\,c=1,\,f(n)=10n$
    $f(n)=\Theta \left(n^{c}\log ^{k}n\right)$ onde $c=1,k=0$
Em seguida, vamos ver se conseguimos satisfazer a condição do caso 2:
    $\log _{b}a=\log _{2}2=1$ e, portanto, $c=\log _{b}a$
Do segundo caso do teorema mestre, segue que
    $T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)=\Theta \left(n^{1}\log ^{1}n\right)=\Theta \left(n\log n\right)$
Assim, a relação de recorrência $T(n)$ está em $\Theta (n\log n)$.
(Este resultado é confirmado pela solução exata da relação de recorrência, que é $T(n)=n+10n\log _{2}n$, assumindo $T(1)=1$.)

#### Exemplo do caso 3

    $T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$
Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:
    $a=2,\,b=2,\,f(n)=n^{2}$
    $f(n)=\Omega \left(n^{c}\right)$, onde $c=2$
Em seguida, vamos ver se a condição do caso 3 é satisfeita:
    $\log _{b}a=\log _{2}2=1$, e portanto, sim, $c>\log _{b}a$
A condição de regularidade também é satisfeita:
    $2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}$, escolhendo $k=1/2$
Então, pelo terceiro caso do teorema mestre:
    $T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).$
Assim, a relação de recorrência $T(n)$ está em $\Theta (n^{2})$, que está em conformidade com o $f(n)$ da fórmula original.
(Esse resultado é confirmado pela solução exata da relação de recorrência, que é $T(n)=2n^{2}-n$, assumindo $T(1)=1$.)

## Equações inadmissíveis

As equações a seguir não podem ser resolvidas utilizando o teorema mestre:
* $T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$
    $a$ não é uma constante; o número de subproblemas deveria ser fixo
* $T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$
    diferença não polinomial entre f(n) e $n^{\log _{b}a}$ (veja abaixo; a versão estendida se aplica)
* $T(n)=0.5T\left({\frac {n}{2}}\right)+n$
    $a<1$ não pode haver menos que um subproblema
* $T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$
    f(n), que é o tempo de combinação (dos subproblema), não é positivo
* $T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)$
    caso 3, mas viola a condição de regularidade.
No segundo exemplo inadmissível acima, a diferença entre $f(n)$ e $n^{\log _{b}a}$ pode ser expressa com a relação ${\frac {f(n)}{n^{\log _{b}a}}}={\frac {n/\log n}{n^{\log _{2}2}}}={\frac {n}{n\log n}}={\frac {1}{\log n}}$. É claro que ${\frac {1}{\log n}}<n^{\epsilon }$ para qualquer constante $\epsilon >0$. Portanto, a diferença não é polinomial e a forma básica do Teorema Mestre não se aplica. A forma estendida (caso 2b) aplica-se, dando a solução $T(n)=\Theta (n\log \log n)$.

## Aplicação em algoritmos comuns

| Algortimo | Relação de recorrência | Tempo de execução | Comentário |
| Pesquisa binária | $T(n)=T\left({\frac {n}{2}}\right)+O(1)$ | $O(\log n)$ | Aplicado o caso do teorema mestre $c=\log _{b}a$, onde $a=1,b=2,c=0,k=0$ |
| Percurso em árvore binária | $T(n)=2T\left({\frac {n}{2}}\right)+O(1)$ | $O(n)$ | Aplicado o caso do teorema mestre $c<\log _{b}a$ onde$a=2,b=2,c=0$ |
| Pesquisa ótima de matriz ordenada | $T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$ | $O(n)$ | Aplica o caso do método de Akra-Bazzi para $p=1$ e $g(u)=\log(u)$ $\Theta (2n-\log n)$ |
| Merge sort | $T(n)=2T\left({\frac {n}{2}}\right)+O(n)$ | $O(n\log n)$ | Aplica o caso do teorema mestre $c=\log _{b}a$, onde $a=2,b=2,c=1,k=0$ |