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.^[1] 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.

Considere um problema que pode ser resolvido usando um algoritmo recursivo como o algoritmo a seguir:

 procedimento p(entrada x de tamanho n):
 se n < alguma constante k:
   Resolver x diretamente, sem recursão
 senão:
   Criar a subproblemas de x, cada um com tamanho n/b
   Chamar o procedimento p recursivamente em cada subproblema
   Combinar os resultados dos subproblemas

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 ${\displaystyle 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 ${\displaystyle f(n)}$. A quantidade total de trabalho realizado pelo algoritmo completo é a soma do trabalho realizado por todos os nós na árvore.${\displaystyle }$${\displaystyle }$${\displaystyle }$O tempo de execução de um algoritmo, como o 'p' acima em uma entrada de tamanho 'n', geralmente denotado por ${\displaystyle T(n)}$, pode ser expresso pela relação de recorrência

${\displaystyle T(n)=aT({\frac {n}{b}})+f(n)}$

onde ${\displaystyle 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.^[2] 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.${\displaystyle }$

${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$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:

${\displaystyle T(n)=aT({\frac {n}{b}})+f(n)}$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$Aqui ${\displaystyle n}$ é o tamanho da entrada de um problema, ${\displaystyle a}$ é o número de subproblemas na recursão, e ${\displaystyle 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, ${\displaystyle T(n)=\Theta (1)}$ quando ${\displaystyle n}$ é menor que algum limite ${\displaystyle \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 ${\displaystyle f(n)}$ relaciona-se com a expoente crítico. (A tabela abaixo utiliza o padrão de big O notation.)${\displaystyle }$${\displaystyle }$

${\displaystyle c_{\operatorname {crit} }=\log _{b}a=\log(\#{\text{subproblemas}})/\log({\text{tamanho relativo do subproblema}})}$

Caso	Descrição	Condição sobre ${\displaystyle f(n)}$ em relação a ${\displaystyle c_{\operatorname {crit} }}$, i.e. ${\displaystyle \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 ${\displaystyle f(n)=O(n^{c})}$ onde ${\displaystyle c<c_{\operatorname {crit} }}$ (limitado superiormente por um polinômio de expoente menor)	... então ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}$ (O termo de divisão não aparece; a estrutura da árvore recursiva domina.)	Se ${\displaystyle b=a^{2}}$ and ${\displaystyle f(n)=O(n^{1/2-\epsilon })}$, então ${\displaystyle T(n)=\Theta (n^{1/2})}$.
2	O trabalho para dividir/recombinar um problema é comparável aos subproblemas.	Quando ${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$ para qualquer ${\displaystyle k\geq 0}$ (faixa limitada pelo polinômio de expoente crítico, vezes zero ou mais opcional ${\displaystyle \log }$s)	... então ${\displaystyle 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 ${\displaystyle b=a^{2}}$ e ${\displaystyle f(n)=\Theta (n^{1/2})}$, então ${\displaystyle T(n)=\Theta (n^{1/2}\log n)}$. Se ${\displaystyle b=a^{2}}$ e ${\displaystyle f(n)=\Theta (n^{1/2}\log n)}$, então ${\displaystyle 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 ${\displaystyle f(n)=\Omega (n^{c})}$onde ${\displaystyle c>c_{\operatorname {crit} }}$ (limitado inferiormente por um polinômio de maior expoente)	... isso não produz necessariamente nada. Se é sabido ainda que ${\displaystyle af\left({\frac {n}{b}}\right)\leq kf(n)}$ para alguma constante ${\displaystyle k<1}$ e suficientemente grande ${\displaystyle n}$ (frequentemente chamado de condição de regularidade) então o total é dominado pelo termo de divisão ${\displaystyle f(n)}$: ${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)}$	Se ${\displaystyle b=a^{2}}$ e ${\displaystyle f(n)=\Omega (n^{1/2+\epsilon })}$ e a condição de regularidade é satisfeita, então ${\displaystyle T(n)=\Theta (f(n))}$.

Uma extensão útil do caso 2 abrange todos os valores de ${\displaystyle k}$^[3]

Caso	${\displaystyle f(n)}$ ${\displaystyle c_{\operatorname {crit} }}$, i.e. ${\displaystyle \log _{b}a}$	Limite do teorema mestre	Exemplos notacionais
2a	Quando ${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$ para qualquer ${\displaystyle k>-1}$	... então${\displaystyle 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.)	${\displaystyle b=a^{2}}$ e${\displaystyle f(n)=\Theta (n^{1/2}/\log ^{1/2}n)}$, então${\displaystyle T(n)=\Theta (n^{1/2}\log ^{1/2}n)}$.
2b	Quando ${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$ fpara ${\displaystyle k=-1}$	... then ${\displaystyle 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 ${\displaystyle b=a^{2}}$ ${\displaystyle f(n)=\Theta (n^{1/2}/\log n)}$, então ${\displaystyle T(n)=\Theta (n^{1/2}\log \log n)}$.
2c	Quando${\displaystyle f(n)=\Theta (n^{c_{\operatorname {crit} }}\log ^{k}n)}$ para qualquer ${\displaystyle k<-1}$	... then ${\displaystyle T(n)=\Theta \left(n^{c_{\operatorname {crit} }}\right)}$ (O limite é o termo de divisão, onde o log desaparece.)	Se ${\displaystyle b=a^{2}}$ e${\displaystyle f(n)=\Theta (n^{1/2}/\log ^{2}n)}$, então ${\displaystyle T(n)=\Theta (n^{1/2})}$.

${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}}$

Como se pode ver a partir da fórmula acima:

${\displaystyle a=8,\,b=2,\,f(n)=1000n^{2}}$, então

${\displaystyle f(n)=O\left(n^{c}\right)}$, onde ${\displaystyle c=2}$

Em seguida, vamos ver se conseguimos satisfazer a condição do caso 1:

${\displaystyle \log _{b}a=\log _{2}8=3>c}$.

Do primeiro caso do teorema mestre, segue que

${\displaystyle 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 é ${\displaystyle T(n)=1001n^{3}-1000n^{2}}$, assumindo ${\displaystyle T(1)=1}$).

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+10n}$

Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:

${\displaystyle a=2,\,b=2,\,c=1,\,f(n)=10n}$

${\displaystyle f(n)=\Theta \left(n^{c}\log ^{k}n\right)}$ onde ${\displaystyle c=1,k=0}$

Em seguida, vamos ver se conseguimos satisfazer a condição do caso 2:

${\displaystyle \log _{b}a=\log _{2}2=1}$ e, portanto, ${\displaystyle c=\log _{b}a}$

Do segundo caso do teorema mestre, segue que

${\displaystyle 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 ${\displaystyle T(n)}$ está em ${\displaystyle \Theta (n\log n)}$.

(Este resultado é confirmado pela solução exata da relação de recorrência, que é ${\displaystyle T(n)=n+10n\log _{2}n}$, assumindo ${\displaystyle T(1)=1}$.)

${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n^{2}}$

Como podemos ver na fórmula acima as variáveis possuem os seguintes valores:

${\displaystyle a=2,\,b=2,\,f(n)=n^{2}}$

${\displaystyle f(n)=\Omega \left(n^{c}\right)}$, onde ${\displaystyle c=2}$

Em seguida, vamos ver se a condição do caso 3 é satisfeita:

${\displaystyle \log _{b}a=\log _{2}2=1}$, e portanto, sim, ${\displaystyle c>\log _{b}a}$

A condição de regularidade também é satisfeita:

${\displaystyle 2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}}$, escolhendo ${\displaystyle k=1/2}$

Então, pelo terceiro caso do teorema mestre:

${\displaystyle T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).}$

Assim, a relação de recorrência ${\displaystyle T(n)}$ está em ${\displaystyle \Theta (n^{2})}$, que está em conformidade com o ${\displaystyle f(n)}$ da fórmula original.

(Esse resultado é confirmado pela solução exata da relação de recorrência, que é ${\displaystyle T(n)=2n^{2}-n}$, assumindo ${\displaystyle T(1)=1}$.)

As equações a seguir não podem ser resolvidas utilizando o teorema mestre:^[4]

• ${\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}$

  ${\displaystyle a}$ não é uma constante; o número de subproblemas deveria ser fixo

• ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}$

  diferença não polinomial entre f(n) e ${\displaystyle n^{\log _{b}a}}$ (veja abaixo; a versão estendida se aplica)

• ${\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n}$

  ${\displaystyle a<1}$ não pode haver menos que um subproblema

• ${\displaystyle 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

• ${\displaystyle 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 ${\displaystyle f(n)}$ e ${\displaystyle n^{\log _{b}a}}$ pode ser expressa com a relação ${\displaystyle {\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 ${\displaystyle {\frac {1}{\log n}}<n^{\epsilon }}$ para qualquer constante ${\displaystyle \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 ${\displaystyle T(n)=\Theta (n\log \log n)}$.

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

• Método de Akra-Bazzi
• Complexidade assintótica

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introdução a Algoritmos, Segunda Edição. MIT Press e McGraw–Hill, 2001. ISBN 0-262-03293-7. Seções 4.3 (O teorema mestre) e 4.4 (Prova do teorema mestre), pp. 73–90.
• Michael T. Goodrich e Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. O teorema mestre (incluindo a versão de Caso 2 incluídos aqui, que é mais forte do que o do CLRS) está no pp. 268-270.

• Teorema Mestre e Exemplos Resolvidos
• Exercícios resolvidos sobre o teorema mestre