ED · Resumo A4 — DCC205 2026/2

Parte 1Divisão e conquista: a forma

A4 · 01

Vocabulário que volta o tempo todo

Relembrando a A2, em uma linha cada:

Notação	Lê-se	Significa
$f = O(g)$	“no máximo $g$”	$f$ cresce até a ordem de $g$
$f = \Omega(g)$	“pelo menos $g$”	$f$ cresce no mínimo na ordem de $g$
$f = \Theta(g)$	“exatamente $g$”	as duas coisas ao mesmo tempo

Não é acasoO enunciado do Teorema Mestre usa as três: $O$ no caso 1, $\Theta$ no caso 2 e $\Omega$ no caso 3. A intuição da Parte 2 mostra por quê — cada caso é uma afirmação diferente sobre quanto $f$ é menor, igual ou maior que o marco.

A4 · 02

O padrão dividir–conquistar–combinar

Os três passos, e o que cada um custa

Passo	O que faz	Custo
1. Dividir	quebrar a instância em $a$ subproblemas de tamanho $n/b$	custo de dividir
2. Conquistar	resolver cada subproblema recursivamente	$a$ chamadas $T(n/b)$
3. Combinar	juntar as respostas dos subproblemas na resposta final	custo de combinar

Dividir e combinar, juntos, custam uma função $f(n)$ fora da recursão.

A4 · 03

A forma geral

Definição

Algoritmos de divisão e conquista geram recorrências do tipo:

$$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n)$$

$a$ — nº de subproblemas, $a \ge 1$: pelo menos um subproblema, senão não há recursão.
$b$ — fator de redução, $b > 1$: o subproblema tem que encolher, senão nunca chega ao caso base.
$f(n)$ — custo de dividir $+$ combinar, assintoticamente positiva.

Como na A3, ignoramos pisos e tetos: escrever $T(\lfloor n/b \rfloor)$ ou $T(\lceil n/b \rceil)$ não muda o resultado assintótico (CLRS, seção 4.6).

A4 · 04

Um exemplo concreto: potenciação recursiva

Calcular $x^y$ dividindo o expoente ao meio:

powerversão ingênua, duas chamadas

int power(int x, unsigned int y) {
if (y == 0)
return 1;
else if (y % 2 == 0)
return power(x, y/2) * power(x, y/2);
else
return x * power(x, y/2) * power(x, y/2);
}

Extraindo a recorrência

Caso base: $y = 0$.
Senão: duas chamadas com expoente $y/2$.
Fora da recursão: uma ou duas multiplicações, custo $O(1)$.

$$T(y) = 2\,T(y/2) + O(1) \qquad \text{ou seja, } a=2,\; b=2,\; f(y)=O(1)$$

A4 · 05

A mesma forma aparece em toda parte

Algoritmo	Recorrência	$a$	$b$
`power` ingênuo	$T(n)=2T(n/2)+O(1)$	2	2
Merge Sort (daqui a algumas aulas)	$T(n)=2T(n/2)+\Theta(n)$	2	2
Busca binária	$T(n)=T(n/2)+\Theta(1)$	1	2
Multiplicação de matrizes (Strassen)	$T(n)=7T(n/2)+\Theta(n^2)$	7	2

Só muda o trio $(a,\,b,\,f(n))$. Resolver a família inteira de uma vez $\Rightarrow$ resolver todos esses algoritmos de uma vez.

A ideia · CLRS, seção 4.5

O Teorema Mestre é uma “receita de bolo”: para recorrências $T(n)=aT(n/b)+f(n)$, com $a\ge 1$, $b>1$ e $f$ assintoticamente positiva, basta memorizar três casos para escrever a resposta — muitas vezes sem lápis e papel.

Antes do enunciado, vamos entender de onde ele vem. A ferramenta é a que já conhecemos da A3: a árvore de recursão — agora aplicada à forma geral, com $a$, $b$ e $f$ simbólicos.

Parte 2Intuição: a árvore de recursão genérica

A4 · 06

Expandindo a recorrência genérica

A raiz trabalha $f(n)$ para dividir e combinar, e dispara $a$ chamadas, cada uma sobre uma instância de tamanho $n/b$. Cada filho, por sua vez, custa $f(n/b)$ e dispara outros $a$ filhos.

Cada nível multiplica o número de nós por a e divide o tamanho por b. A coluna da direita é o custo somado do nível inteiro.

A4 · 07

Altura e número de folhas

Altura

O tamanho cai de $n$ para $n/b$, $n/b^2$, … e chega a 1 quando $n/b^h = 1$:

$$h = \log_b n \ \text{ níveis.}$$

Folhas

Cada nível multiplica o nº de nós por $a$. No último nível:

$$a^{\log_b n} = n^{\log_b a} \ \text{ folhas.}$$

A identidade que sustenta a aula $$a^{\log_b n} = n^{\log_b a}$$

Para conferir, tome $\log_b$ dos dois lados: à esquerda sai $\log_b n \cdot \log_b a$, à direita $\log_b a \cdot \log_b n$.

Custo total das folhas: $n^{\log_b a}\cdot\Theta(1) = \Theta\!\left(n^{\log_b a}\right)$.

A4 · 08

Somando a árvore inteira

Somando o custo de cada nível, de cima a baixo:

Nível	Custo do nível
0	$f(n)$
1	$a\,f(n/b)$
$j$	$a^{j} f(n/b^{j})$
folhas	$\Theta\!\left(n^{\log_b a}\right)$

Custo total · CLRS, eq. 4.21 $$T(n) = \underbrace{\Theta\!\left(n^{\log_b a}\right)}_{\text{folhas}} + \underbrace{\sum_{j=0}^{\log_b n - 1} a^{j} f\!\left(\frac{n}{b^{j}}\right)}_{\text{níveis internos}}$$

O primeiro termo é o custo da recursão em si: o trabalho de chegar até os casos base.
O segundo é o custo de dividir e combinar acumulado em todos os níveis internos.

A pergunta central do teoremaA complexidade final depende de quem domina essa soma. Ou seja: quem cresce mais rápido, $n^{\log_b a}$ ou $f(n)$? Todo o resto da aula é responder isso em três cenários.

A4 · 09

Quem é $n^{\log_b a}$

O expoente $\log_b a$ mede o balanço entre criar e encolher: $a$ é a velocidade com que a árvore se multiplica (filhos por nó) e $b$ a velocidade com que cada problema encolhe.

$a$	$b$	$n^{\log_b a}$	Leitura
2	2	$n^{\log_2 2}=n$	dobra e divide ao meio: equilíbrio linear
4	2	$n^{\log_2 4}=n^2$	multiplica rápido demais: árvore “pesada”
1	2	$n^{\log_2 1}=n^0=1$	um único ramo: árvore “magra”

$n^{\log_b a}$ é exatamente o nº de folhas — o “peso morto” inevitável da recursão, que existiria mesmo se $f$ fosse gratuita. Daqui para frente vamos chamá-lo de marco.

A4 · 10

O cabo de guerra: $f(n)$ contra o marco

Os três desfechos

Caso 1 — as folhas ganham ($f$ é polinomialmente menor) $\Rightarrow$ resposta $\Theta\!\left(n^{\log_b a}\right)$.
Caso 2 — empate ($f=\Theta(n^{\log_b a})$) $\Rightarrow$ a resposta ganha um fator $\log n$.
Caso 3 — a raiz ganha ($f$ é polinomialmente maior) $\Rightarrow$ resposta $\Theta(f(n))$.

Nas palavras do CLRS (p. 94): “intuitivamente, a maior das duas funções determina a solução”. Vamos ver cada caso na árvore.

Parte 3Os três casos, vistos na árvore

A4 · 11

Caso 1 — o custo cresce descendo a árvore

Suponha $f$ pequena: cada nível interno custa pouco perto do que vem abaixo.

Soma geométrica crescente: o último termo domina, e o último termo são as folhas.

Conclusão do caso 1

Se $f(n)$ é “suficientemente menor” que $n^{\log_b a}$, então

$$T(n) = \Theta\!\left(n^{\log_b a}\right).$$

Leitura algorítmica: o gargalo é a explosão de subproblemas, não o trabalho de dividir e combinar.

O “suficientemente menor” será tornado preciso no enunciado: menor por um fator polinomial $n^{\varepsilon}$. Exemplo que já conhecemos: $T(n)=2T(n/2)+O(1)$ — o power ingênuo — com $f$ constante e marco $n^{\log_2 2}=n$, logo $T(n)=\Theta(n)$.

A4 · 12

Caso 2 — todos os níveis custam o mesmo

Agora suponha $f(n)=\Theta\!\left(n^{\log_b a}\right)$: raiz e folhas empatam.

Todos os log_b n níveis contribuem igualmente: a soma vira custo por nível × número de níveis.

Conclusão do caso 2

Se $f(n)=\Theta\!\left(n^{\log_b a}\right)$, então

$$T(n) = \Theta\!\left(n^{\log_b a}\,\log n\right).$$

Ninguém domina: são $\Theta(\log n)$ níveis, cada um custando $\Theta(n^{\log_b a})$.

É o caso do Merge Sort: $T(n)=2T(n/2)+\Theta(n)$, com $n^{\log_2 2}=n=\Theta(f(n))$, logo $T(n)=\Theta(n\log n)$. A base do logaritmo não importa dentro de $\Theta$ — muda só uma constante multiplicativa.

O erro mais comum do teoremaNo caso 2 a resposta não é $\Theta(n^{\log_b a})$. Esquecer o fator $\log n$ é o deslize número um na aplicação — $\Theta(n^{\log_b a})$ é a resposta do caso 1.

A4 · 13

Caso 3 — a raiz domina, com uma condição

Agora $f$ é grande: a raiz já faz a maior parte do trabalho.

Soma geométrica decrescente: o primeiro termo domina, e o primeiro termo é a raiz.

Conclusão do caso 3

Se $f(n)$ é “suficientemente maior” que $n^{\log_b a}$ e vale a condição de regularidade

$$a\,f(n/b) \;\le\; c\,f(n)$$

para algum $c < 1$ e todo $n$ suficientemente grande,

então $T(n)=\Theta(f(n))$.

A regularidade garante exatamente o desenho acima: cada nível custa no máximo uma fração fixa $c$ do anterior. Polinômios “bem comportados” costumam satisfazê-la — e vamos verificar explicitamente nos exemplos.

O $c$ tem que ser estritamente menor que 1Com $c=1$ a soma não seria decrescente: seriam $\log_b n$ níveis iguais, o que daria um fator $\log$ extra — ou seja, o caso 2, não o caso 3. Afirmar a regularidade com $c=1$ é erro.

A4 · 14

Aviso honesto, e um checkpoint

Isto foi intuição, não demonstração

O que fizemos foi ilustrar o mecanismo do teorema com a árvore de recursão. A demonstração formal (CLRS, seção 4.6) trata pisos e tetos, domínios de validade e as desigualdades com cuidado — e não faz parte do escopo da disciplina.

Mas a intuição captura a ideia central da prova: somar a árvore nível a nível e classificar a soma geométrica — crescente, constante ou decrescente.

Checkpoint · verdadeiro ou falso

Afirmação	Veredito
“$n^{\log_b a}$ conta as folhas da árvore de recursão.”	Verdadeiro — $a^{\log_b n}=n^{\log_b a}$.
“No caso 2, a resposta é $\Theta(f(n))$.”	Falso — é $\Theta(n^{\log_b a}\log n)$: todos os níveis contribuem.
“No caso 3, basta $f$ crescer mais que $n^{\log_b a}$.”	Falso — falta a regularidade, e o “mais” precisa ser polinomial.

Parte 4O enunciado formal

A4 · 15

Teorema Mestre (Teorema 4.1, CLRS)

Enunciado

Sejam $a\ge 1$ e $b>1$ constantes, $f(n)$ assintoticamente positiva, e

$$T(n) = a\,T(n/b) + f(n)$$

com $n/b$ interpretado como $\lfloor n/b \rfloor$ ou $\lceil n/b \rceil$. Então:

Se $f(n)=O\!\left(n^{\log_b a-\varepsilon}\right)$ para alguma constante $\varepsilon > 0$, então $T(n)=\Theta\!\left(n^{\log_b a}\right)$.
Se $f(n)=\Theta\!\left(n^{\log_b a}\right)$, então $T(n)=\Theta\!\left(n^{\log_b a}\log n\right)$.
Se $f(n)=\Omega\!\left(n^{\log_b a+\varepsilon}\right)$ para alguma constante $\varepsilon > 0$, e $a f(n/b)\le c f(n)$ para algum $c<1$ e todo $n$ suficientemente grande, então $T(n)=\Theta(f(n))$.

A4 · 16

O papel do $n^{\varepsilon}$: “polinomialmente” menor ou maior

Nos casos 1 e 3 não basta $f$ ser menor (ou maior) que o marco:

Caso 1 exige $f(n)=O\!\left(n^{\log_b a-\varepsilon}\right)$: menor por um fator polinomial $n^{\varepsilon}$.
Caso 3 exige $f(n)=\Omega\!\left(n^{\log_b a+\varepsilon}\right)$: maior por um fator polinomial $n^{\varepsilon}$.

Contra-exemplo clássico

$\log n$ cresce mais que $1$, mas não polinomialmente mais:

$$\log n = O(n^{\varepsilon}) \quad \text{para \textit{todo} } \varepsilon > 0.$$

Diferenças só logarítmicas não ativam os casos 1 e 3.

Guarde este fatoEle vai derrubar o Exemplo 4 e o desafio de casa. Sempre que a diferença entre $f$ e o marco for um fator $\log$, o teorema não decide.

A4 · 17

O teorema não cobre tudo: as lacunas

Entre os casos há faixas descobertas: f maior que o marco, mas não polinomialmente maior — e o simétrico para menor.

Nessas lacunas — ou se a regularidade falhar — o Teorema Mestre não decide. A saída é voltar às ferramentas da A3: árvore de recursão ou substituição.

A4 · 18

Receita de aplicação

Cinco passos · use sempre nesta ordem

Identifique $a$, $b$ e $f(n)$ na recorrência.
Calcule o marco $n^{\log_b a}$.
Compare $f(n)$ com o marco:
- polinomialmente menor $\Rightarrow$ caso 1;
- mesma ordem $\Rightarrow$ caso 2;
- polinomialmente maior $\Rightarrow$ candidato a caso 3.
Se caso 3: verifique a regularidade $a f(n/b)\le c f(n)$ com $c < 1$.
Escreva a resposta — ou declare que o teorema não se aplica.

Agora vamos rodar essa receita em quatro exemplos — os mesmos da seção 4.5 do CLRS.

Parte 5Exemplos resolvidos

A4 · 19

Exemplo 1 — $T(n)=9\,T(n/3)+n$

Passos 1 e 2 · identificar e calcular o marco $$a=9,\qquad b=3,\qquad f(n)=n$$ $$n^{\log_b a} = n^{\log_3 9} = n^2$$

Passo 3 · comparar

$f(n)=n$ contra o marco $n^2$: $n$ é polinomialmente menor — sobra um fator $n^{\varepsilon}$ inteiro, qualquer $\varepsilon \le 1$ serve. Verificação formal com $\varepsilon=1$:

$$f(n)=n=O\!\left(n^{2-1}\right)=O\!\left(n^{\log_3 9-\varepsilon}\right) \quad \checkmark$$

Caso 1 $\Rightarrow$ as folhas dominam $$T(n) = 9\,T(n/3)+n = \Theta\!\left(n^{\log_3 9}\right) = \Theta\!\left(n^2\right)$$

Leitura: com $a=9$ filhos encolhendo só por $b=3$, a árvore engorda rápido — são $n^{\log_3 9}=n^2$ folhas, e o custo linear de dividir/combinar é irrelevante perto disso. Conferindo com a intuição: as barras crescem para baixo, com razão $a f(n/b)/f(n) = 9/3 = 3 > 1$.

A4 · 20

Exemplo 2 — $T(n)=T(2n/3)+1$

Passos 1 e 2 $$a=1,\qquad b=\tfrac{3}{2},\qquad f(n)=1$$ $$n^{\log_b a} = n^{\log_{3/2} 1} = n^0 = 1$$

Passo 3 · comparar

$f(n)=1$ contra o marco $1$: mesma ordem de crescimento, $f(n)=\Theta(1)=\Theta(n^{\log_b a})$ $\Rightarrow$ caso 2.

Caso 2 $\Rightarrow$ o empate paga $\log n$ $$T(n)=T(2n/3)+1=\Theta\!\left(n^{\log_b a}\log n\right)=\Theta(1\cdot\log n)=\Theta(\log n)$$

A árvore aqui é “magra”: um único ramo de $\log_{3/2} n = \Theta(\log n)$ níveis, cada um custando $\Theta(1)$. É o esqueleto da busca binária — lá com $b=2$: um subproblema, trabalho constante por nível.

Cuidado com a leitura de $b$O subproblema tem tamanho $\tfrac{2n}{3}=\dfrac{n}{3/2}$, logo $b=\tfrac{3}{2}>1$ — e não $b=3$. E $a=1$ é permitido: a exigência é $a\ge 1$.

A4 · 21

Exemplo 3 — $T(n)=3\,T(n/4)+n\log n$

Passos 1 e 2 $$a=3,\qquad b=4,\qquad f(n)=n\log n$$ $$n^{\log_b a} = n^{\log_4 3} = O\!\left(n^{0{,}793}\right)$$

Passo 3 · comparar

$f(n)=n\log n$ cresce mais que $n^{0,793}$ — e a diferença é um fator $n^{0{,}207}\log n$, polinomial de sobra. Formalmente $f(n)=\Omega\!\left(n^{\log_4 3+\varepsilon}\right)$ com, por exemplo, $\varepsilon=0{,}2$. Candidato a caso 3.

Passo 4 · verificando a regularidade

Queremos $c < 1$ com $3f(n/4)\le c\,f(n)$ para $n$ grande:

$$3f(n/4) = 3\,\frac{n}{4}\log\frac{n}{4}$$ $$\le 3\,\frac{n}{4}\log n \;=\; \frac{3}{4}\,n\log n \;=\; \frac{3}{4}\,f(n)$$

Funciona com $c=\tfrac{3}{4} < 1$ — exatamente como no CLRS, p. 95. $\checkmark$

Caso 3 $\Rightarrow$ a raiz domina $$T(n)=3\,T(n/4)+n\log n=\Theta(f(n))=\Theta(n\log n)$$

O passo que ninguém pode pularA desigualdade $\log\frac{n}{4}\le\log n$ é o que faz a conta fechar — o $\log$ encolhe junto com o argumento, e é dele que sai a folga. Sem exibir um $c$ concreto, a resposta do caso 3 fica incompleta.

A4 · 22

Exemplo 4 — $T(n)=2\,T(n/2)+n\log n$: o teorema falha

Passos 1 e 2 $$a=2,\qquad b=2,\qquad f(n)=n\log n$$ $$n^{\log_b a}=n^{\log_2 2}=n$$

Passo 3 · a comparação que não fecha

$f(n)=n\log n$ cresce mais que $n$… caso 3? Para o caso 3 precisamos de $f(n)=\Omega\!\left(n^{1+\varepsilon}\right)$ para algum $\varepsilon > 0$. Mas

$$\frac{f(n)}{n}=\log n, \qquad \log n = O(n^{\varepsilon}) \ \text{ para \textit{todo} } \varepsilon > 0$$

A folga é só logarítmica, não polinomial.

Conclusão

$T(n)=2T(n/2)+n\log n$ cai na lacuna entre os casos 2 e 3: $f$ é maior que $n^{\log_b a}$, mas não polinomialmente maior. Nenhum caso do teorema decide esta recorrência.

“Não se aplica” $\ne$ “não tem solução”Com a árvore de recursão — a ferramenta da A3 — mostra-se que $T(n)=\Theta(n\log^2 n)$ (exercício 4.6-2 do CLRS). O Teorema Mestre é uma receita rápida, não universal: reconhecer quando ele falha faz parte de saber usá-lo.

Parte 6Prática, armadilhas e quadro final

A4 · Exercício

A mesma recorrência, com $f$ cada vez maior

Exercício 4.5-1 do CLRS. Resolva as quatro:

	Recorrência
(a)	$T(n)=2\,T(n/4)+1$
(b)	$T(n)=2\,T(n/4)+\sqrt{n}$
(c)	$T(n)=2\,T(n/4)+n$
(d)	$T(n)=2\,T(n/4)+n^2$

Dica: o marco é o mesmo nas quatro. Calcule-o uma vez e compare.

O marco, calculado uma vez só $$n^{\log_4 2}=n^{1/2}=\sqrt{n}$$

(a) $f(n)=1$ · caso 1

$1$ é polinomialmente menor que $\sqrt{n}$: $1=O\!\left(n^{1/2-\varepsilon}\right)$ com $\varepsilon=\tfrac12$.

$$T(n)=\Theta\!\left(n^{\log_4 2}\right)=\Theta(\sqrt{n})$$

(b) $f(n)=\sqrt{n}$ · caso 2

Empate exato: $f(n)=\sqrt{n}=\Theta\!\left(n^{\log_4 2}\right)$.

$$T(n)=\Theta\!\left(\sqrt{n}\,\log n\right)$$

Polinomialmente maior, com $\varepsilon=\tfrac12$. Regularidade:

$$2f(n/4)=2\cdot\frac{n}{4}=\frac{n}{2}=\frac12 f(n) \;\Rightarrow\; c=\tfrac12 < 1 \quad \checkmark$$ $$T(n)=\Theta(f(n))=\Theta(n)$$

(d) $f(n)=n^2$ · caso 3

Polinomialmente maior, com $\varepsilon=\tfrac32$. Regularidade:

$$2f(n/4)=2\cdot\frac{n^2}{16}=\frac{n^2}{8}=\frac18 f(n) \;\Rightarrow\; c=\tfrac18 < 1 \quad \checkmark$$ $$T(n)=\Theta\!\left(n^2\right)$$

A progressão que o exercício ensina$f = 1 \to \sqrt{n} \to n \to n^2$ leva a resposta pelos casos 1 → 2 → 3 → 3: quanto maior $f$, mais a raiz manda. E repare que $a$ e $b$ nunca mudaram — só o trabalho de dividir e combinar.

A4 · 23

Armadilhas comuns

Erro	Por quê
Esquecer o $\log n$ do caso 2	$\Theta(n^{\log_b a})$ é a resposta do caso 1, não do 2.
Achar que “maior” basta no caso 3	$n\log n$ vs. $n$: folga logarítmica não é polinomial (Exemplo 4).
Usar $c=1$ na regularidade	Exige-se $c$ estritamente menor que 1.
Ler $b$ errado	Em $T(2n/3)$ o fator é $b=3/2$ — o tamanho vira $n/(3/2)$ — e não $b=3$.
Aplicar fora da forma	O teorema pede subproblemas de mesmo tamanho $n/b$ e $a$ constante.

A4 · 24

Quando o Teorema Mestre não se aplica

Recorrência	Por quê
$T(n)=2T(n/2)+n\log n$	lacuna entre os casos 2 e 3
$T(n)=T(n/3)+T(2n/3)+n$	subproblemas de tamanhos diferentes
$T(n)=T(n-1)+n$	redução subtrativa, não por fator $b>1$
$T(n)=0{,}5\,T(n/2)+n$	$a=0{,}5<1$: “meio subproblema” não existe
$T(n)=2T(n/2)-n$	$f$ negativa: não é custo

Nesses casos, voltamos às ferramentas da A3: árvore de recursão e substituição. Note que a terceira linha é exatamente a família $T(n-1)+\dots$ que a A3 resolvia por expansão — ela nunca esteve no escopo do teorema.

A4 · 25

Os três casos em uma tabela

Caso	Condição sobre $f$	Extra	Resposta
1	$f(n)=O\!\left(n^{\log_b a-\varepsilon}\right)$	—	$\Theta\!\left(n^{\log_b a}\right)$
2	$f(n)=\Theta\!\left(n^{\log_b a}\right)$	—	$\Theta\!\left(n^{\log_b a}\log n\right)$
3	$f(n)=\Omega\!\left(n^{\log_b a+\varepsilon}\right)$	$a f(n/b)\le c f(n)$, $c<1$	$\Theta(f(n))$

Em uma frase por caso: 1 as folhas dominam · 2 empate, multiplica por $\log n$ · 3 a raiz domina.

A4 · Desafio

Para pensar antes da próxima aula

Exercício 4.5-4 do CLRS. O Teorema Mestre pode ser aplicado a

$$T(n)=4\,T(n/2)+n^2\log n \;?$$

Por quê? Se não puder, encontre um limite superior assintótico.

Dicas

Calcule o marco $n^{\log_b a}$ e compare com $f$.
Este exemplo é primo do nosso Exemplo 4 — repare no formato da diferença entre $f$ e o marco.

Quem quiser conferir a resposta: a árvore de recursão da A3 resolve. Vale trazer a solução para discutir.

A4 · 26

O que levar desta aula, e referências

Cinco linhas

Divisão e conquista gera recorrências $T(n)=aT(n/b)+f(n)$; o trio $(a,b,f)$ determina tudo.
A árvore de recursão explica o teorema: folhas $n^{\log_b a}$ de um lado, custo de dividir/combinar do outro.
A resposta é um cabo de guerra entre $f(n)$ e $n^{\log_b a}$: ganha o maior; empate paga $\log n$.
Casos 1 e 3 exigem folga polinomial ($n^{\varepsilon}$); o caso 3 exige ainda regularidade com $c<1$.
O teorema não cobre tudo — há lacunas, e reconhecê-las faz parte do método.

Leitura recomendada · Cormen et al., 3ª ed.

Seção 4.5 — The master method: a aula inteira está lá.
Seção 4.4 — Recursion trees: a intuição, já vista na A3.
Exercícios 4.5-1 a 4.5-4 — o 4.5-1 foi feito em sala, o 4.5-4 é o desafio acima.
Opcional, para os curiosos: seção 4.6 — a demonstração do Teorema 4.1.

Próxima aula: tipos abstratos de dados e as primeiras estruturas — listas, pilhas e filas, onde os custos que aprendemos a medir passam a orientar escolhas de projeto.

FechoChecklist da aula

Revisão

Checklist da A4

Se você consegue responder tudo abaixo sem consultar, a aula está fechada.

Pergunta	Onde está
Dizer qual notação ($O$, $\Theta$, $\Omega$) aparece em cada caso, e por quê	Vocabulário
Descrever os três passos de divisão e conquista e onde entra $f(n)$	Dividir, conquistar, combinar
Escrever a forma geral e justificar $a\ge1$ e $b>1$	A forma geral
Extrair $a$, $b$ e $f$ do `power` ingênuo	Potenciação recursiva
Achar a altura da árvore resolvendo $n/b^h=1$	Altura e folhas
Provar a identidade $a^{\log_b n}=n^{\log_b a}$ tomando $\log_b$ dos dois lados	Altura e folhas
Escrever a soma da árvore separando folhas e níveis internos	Somando a árvore
Explicar o que o expoente $\log_b a$ mede, com os três exemplos de $(a,b)$	Quem é o marco
Enunciar o cabo de guerra em uma frase	O cabo de guerra
Desenhar as barras dos três casos e dizer qual termo domina em cada um	Casos 1, 2 e 3
Dizer por que o caso 2 multiplica por $\log n$ e por que a base do log não importa	Caso 2
Enunciar a condição de regularidade e explicar por que $c=1$ não serve	Caso 3
Escrever os três casos do Teorema 4.1 com as condições corretas	Teorema 4.1
Explicar por que $\log n = O(n^{\varepsilon})$ impede os casos 1 e 3	O papel do $n^{\varepsilon}$
Dizer onde ficam as duas lacunas e o que fazer quando se cai nelas	As lacunas
Executar os cinco passos da receita numa recorrência nova	Receita de aplicação
Resolver $9T(n/3)+n$ exibindo o $\varepsilon$ usado	Exemplo 1
Ler $b=3/2$ em $T(2n/3)$ e concluir $\Theta(\log n)$	Exemplo 2
Verificar a regularidade de $3T(n/4)+n\log n$ exibindo $c=3/4$	Exemplo 3
Mostrar que $2T(n/2)+n\log n$ cai na lacuna, e dar a resposta pela árvore	Exemplo 4
Resolver as quatro variantes de $2T(n/4)+f$ com um único marco	Exercício · quatro $f$
Listar as cinco armadilhas e dizer qual delas erra o $b$	Armadilhas comuns
Dar três recorrências fora do escopo do teorema, com o motivo de cada uma	Quando não se aplica
Reproduzir de memória a tabela dos três casos	Os três casos em uma tabela

Notação	Lê-se	Significa
\(f = O(g)\)	“no máximo \(g\)”	\(f\) cresce até a ordem de \(g\)
\(f = \Omega(g)\)	“pelo menos \(g\)”	\(f\) cresce no mínimo na ordem de \(g\)
\(f = \Theta(g)\)	“exatamente \(g\)”	as duas coisas ao mesmo tempo

Nível	Custo do nível
0	\(f(n)\)
1	\(a\,f(n/b)\)
\(j\)	\(a^{j} f(n/b^{j})\)
folhas	\(\Theta\!\left(n^{\log_b a}\right)\)

\(a\)	\(b\)	\(n^{\log_b a}\)	Leitura
2	2	\(n^{\log_2 2}=n\)	dobra e divide ao meio: equilíbrio linear
4	2	\(n^{\log_2 4}=n^2\)	multiplica rápido demais: árvore “pesada”
1	2	\(n^{\log_2 1}=n^0=1\)	um único ramo: árvore “magra”

Afirmação	Veredito
“\(n^{\log_b a}\) conta as folhas da árvore de recursão.”	Verdadeiro — \(a^{\log_b n}=n^{\log_b a}\).
“No caso 2, a resposta é \(\Theta(f(n))\).”	Falso — é \(\Theta(n^{\log_b a}\log n)\): todos os níveis contribuem.
“No caso 3, basta \(f\) crescer mais que \(n^{\log_b a}\).”	Falso — falta a regularidade, e o “mais” precisa ser polinomial.

Erro	Por quê
Esquecer o \(\log n\) do caso 2	\(\Theta(n^{\log_b a})\) é a resposta do caso 1, não do 2.
Achar que “maior” basta no caso 3	\(n\log n\) vs. \(n\): folga logarítmica não é polinomial (Exemplo 4).
Usar \(c=1\) na regularidade	Exige-se \(c\) estritamente menor que 1.
Ler \(b\) errado	Em \(T(2n/3)\) o fator é \(b=3/2\) — o tamanho vira \(n/(3/2)\) — e não \(b=3\).
Aplicar fora da forma	O teorema pede subproblemas de mesmo tamanho \(n/b\) e \(a\) constante.

Teorema Mestrea receita de bolo

Vocabulário que volta o tempo todo

O padrão dividir–conquistar–combinar

A forma geral

Um exemplo concreto: potenciação recursiva

A mesma forma aparece em toda parte

Expandindo a recorrência genérica

Altura e número de folhas

Somando a árvore inteira

Quem é \(n^{\log_b a}\)

O cabo de guerra: \(f(n)\) contra o marco

Caso 1 — o custo cresce descendo a árvore

Caso 2 — todos os níveis custam o mesmo

Caso 3 — a raiz domina, com uma condição

Aviso honesto, e um checkpoint

Teorema Mestre (Teorema 4.1, CLRS)

O papel do \(n^{\varepsilon}\): “polinomialmente” menor ou maior

O teorema não cobre tudo: as lacunas

Receita de aplicação

Exemplo 1 — \(T(n)=9\,T(n/3)+n\)

Exemplo 2 — \(T(n)=T(2n/3)+1\)

Exemplo 3 — \(T(n)=3\,T(n/4)+n\log n\)

Exemplo 4 — \(T(n)=2\,T(n/2)+n\log n\): o teorema falha

A mesma recorrência, com \(f\) cada vez maior

Armadilhas comuns

Quando o Teorema Mestre não se aplica

Os três casos em uma tabela

Para pensar antes da próxima aula

O que levar desta aula, e referências

Checklist da A4

Passo	O que faz	Custo
1. Dividir	quebrar a instância em \(a\) subproblemas de tamanho \(n/b\)	custo de dividir
2. Conquistar	resolver cada subproblema recursivamente	\(a\) chamadas \(T(n/b)\)
3. Combinar	juntar as respostas dos subproblemas na resposta final	custo de combinar

Algoritmo	Recorrência	\(a\)	\(b\)
`power` ingênuo	\(T(n)=2T(n/2)+O(1)\)	2	2
Merge Sort (daqui a algumas aulas)	\(T(n)=2T(n/2)+\Theta(n)\)	2	2
Busca binária	\(T(n)=T(n/2)+\Theta(1)\)	1	2
Multiplicação de matrizes (Strassen)	\(T(n)=7T(n/2)+\Theta(n^2)\)	7	2

	Recorrência
(a)	\(T(n)=2\,T(n/4)+1\)
(b)	\(T(n)=2\,T(n/4)+\sqrt{n}\)
(c)	\(T(n)=2\,T(n/4)+n\)
(d)	\(T(n)=2\,T(n/4)+n^2\)

Recorrência	Por quê
\(T(n)=2T(n/2)+n\log n\)	lacuna entre os casos 2 e 3
\(T(n)=T(n/3)+T(2n/3)+n\)	subproblemas de tamanhos diferentes
\(T(n)=T(n-1)+n\)	redução subtrativa, não por fator \(b>1\)
\(T(n)=0{,}5\,T(n/2)+n\)	\(a=0{,}5<1\): “meio subproblema” não existe
\(T(n)=2T(n/2)-n\)	\(f\) negativa: não é custo

Caso	Condição sobre \(f\)	Extra	Resposta
1	\(f(n)=O\!\left(n^{\log_b a-\varepsilon}\right)\)	—	\(\Theta\!\left(n^{\log_b a}\right)\)
2	\(f(n)=\Theta\!\left(n^{\log_b a}\right)\)	—	\(\Theta\!\left(n^{\log_b a}\log n\right)\)
3	\(f(n)=\Omega\!\left(n^{\log_b a+\varepsilon}\right)\)	\(a f(n/b)\le c f(n)\), \(c<1\)	\(\Theta(f(n))\)

Pergunta	Onde está
Dizer qual notação (\(O\), \(\Theta\), \(\Omega\)) aparece em cada caso, e por quê	Vocabulário
Descrever os três passos de divisão e conquista e onde entra \(f(n)\)	Dividir, conquistar, combinar
Escrever a forma geral e justificar \(a\ge1\) e \(b>1\)	A forma geral
Extrair \(a\), \(b\) e \(f\) do `power` ingênuo	Potenciação recursiva
Achar a altura da árvore resolvendo \(n/b^h=1\)	Altura e folhas
Provar a identidade \(a^{\log_b n}=n^{\log_b a}\) tomando \(\log_b\) dos dois lados	Altura e folhas
Escrever a soma da árvore separando folhas e níveis internos	Somando a árvore
Explicar o que o expoente \(\log_b a\) mede, com os três exemplos de \((a,b)\)	Quem é o marco
Enunciar o cabo de guerra em uma frase	O cabo de guerra
Desenhar as barras dos três casos e dizer qual termo domina em cada um	Casos 1, 2 e 3
Dizer por que o caso 2 multiplica por \(\log n\) e por que a base do log não importa	Caso 2
Enunciar a condição de regularidade e explicar por que \(c=1\) não serve	Caso 3
Escrever os três casos do Teorema 4.1 com as condições corretas	Teorema 4.1
Explicar por que \(\log n = O(n^{\varepsilon})\) impede os casos 1 e 3	O papel do \(n^{\varepsilon}\)
Dizer onde ficam as duas lacunas e o que fazer quando se cai nelas	As lacunas
Executar os cinco passos da receita numa recorrência nova	Receita de aplicação
Resolver \(9T(n/3)+n\) exibindo o \(\varepsilon\) usado	Exemplo 1
Ler \(b=3/2\) em \(T(2n/3)\) e concluir \(\Theta(\log n)\)	Exemplo 2
Verificar a regularidade de \(3T(n/4)+n\log n\) exibindo \(c=3/4\)	Exemplo 3
Mostrar que \(2T(n/2)+n\log n\) cai na lacuna, e dar a resposta pela árvore	Exemplo 4
Resolver as quatro variantes de \(2T(n/4)+f\) com um único marco	Exercício · quatro \(f\)
Listar as cinco armadilhas e dizer qual delas erra o \(b\)	Armadilhas comuns
Dar três recorrências fora do escopo do teorema, com o motivo de cada uma	Quando não se aplica
Reproduzir de memória a tabela dos três casos	Os três casos em uma tabela