ED · Resumo A2 — DCC205 2026/2

A2 · 01

Por que a ordem de crescimento importa

O experimento de abertura da aula compara duas máquinas absurdamente desiguais rodando dois algoritmos de ordenação diferentes.

Computador A · rápido

$10^{10}$ instruções por segundo.

Roda insertion sort: $\approx 2n^2$ instruções.

Computador B · 1000× mais lento

$10^{7}$ instruções por segundo.

Roda merge sort: $\approx 50\,n\lg n$ instruções.

Exemplo · ordenando $n=10^7$ números

Computador A, o rápido:

$$\frac{2\cdot(10^7)^2}{10^{10}} = 20\,000\ \text{s} \approx 5{,}5\ \text{horas}$$

Computador B, o lento:

$$\frac{50\cdot 10^7\lg 10^7}{10^7} \approx 1\,163\ \text{s} \approx 20\ \text{min}$$

A moral do slide: a ordem de crescimento do algoritmo venceu um hardware 1000× mais rápido. Trocar $n^2$ por $n\lg n$ valeu mais que trocar a máquina.

A2 · 02

O que a assintótica joga fora

Duas observações da aula, e cada uma descarta um pedaço da função de custo.

Observação 1 — termos que não dependem de $n$

Exemplo · $f(n)=2n-1$

Comparando $f(n)=2n-1$ com $2n$, ou seja, medindo o peso do $-1$:

$n$	$f(n)=2n-1$	$2n$	diferença relativa
10	19	20	5%
1 000	1 999	2 000	0,05%
1 000 000	1 999 999	2 000 000	0,00005%

O $-1$ continua lá, mas some proporcionalmente: termos que não dependem de $n$ tornam-se irrelevantes quando $n$ cresce.

Observação 2 — a constante que multiplica $n$

O que o gráfico mostra

Plotando $2n-1$ e $n$ no mesmo eixo, para $n$ de 0 a 50:

as duas retas têm inclinações diferentes…
…mas ambas crescem de forma linear: dobrando $n$, o custo dobra;
a constante muda a inclinação da reta, não a forma do crescimento.

Logo: para comparar formas de crescimento, podemos ignorar constantes multiplicativas.

A2 · 03

Formas de crescimento diferentes

Descartadas constantes e termos de menor ordem, o que sobra é a forma da curva — e formas diferentes se separam violentamente.

$n$	$\lg n$	$n^2$	$2^n$
10	3,3	100	1 024
20	4,3	400	$\approx 10^{6}$
50	5,6	2 500	$\approx 10^{15}$
100	6,6	10 000	$\approx 10^{30}$

No gráfico das cinco curvas — $\lg n$, $n$, $n\lg n$, $n^2$, $2^n$ — até $n=20$ a exponencial já saiu da tela e a logarítmica mal descolou do eixo.

É a forma da curva — não a constante — que decide quem vence quando $n$ cresce.

A2 · 04

A estratégia: três conjuntos de funções

A ideia

Analisar eficiência é olhar o custo em relação ao tamanho da entrada $n$…
…quando $n$ cresce sem limite (“no limite”, assintoticamente).
Nesse regime, termos de menor ordem e constantes multiplicativas são descartados — só sobrevive a ordem de crescimento.

Então definimos conjuntos de funções que capturam “crescer no máximo como $f$”, “no mínimo como $f$” e “exatamente como $f$”, e enquadramos a função de custo do algoritmo em um deles.

Notação	Lê-se	Papel
$O$	“big oh”	teto
$\Omega$	“big omega”	piso
$\Theta$	“theta”	sanduíche

A2 · 05

Notação $O$ — o teto

Intuição primeiro

Dizer que $g(n)$ é $O(f(n))$ significa:

“A partir de certo ponto, $g$ nunca ultrapassa um múltiplo constante de $f$.”

$f$ funciona como um teto de crescimento para $g$;
“a partir de certo ponto”: ignoramos o comportamento para $n$ pequeno;
“múltiplo constante”: ignoramos constantes multiplicativas.

Exemplo mental: $g(n)=2n$ cresce “no máximo como” $f(n)=n$. Basta usar o múltiplo $2f(n)$.

Definição formal $$O(f(n)) := \{\, g(n) \;:\; \exists\, c,m>0 \ \text{t.q.}\ g(n)\le c\,f(n),\ \forall\, n\ge m \,\}$$

Lendo por partes:

$O(f(n))$ é um conjunto de funções — as $g(n)$ que satisfazem a condição;
existem constantes positivas $c$ e $m$ — basta alguma escolha funcionar;
se $n\ge m$, então $g(n)\le c\,f(n)$ — o teto vale para toda entrada suficientemente grande.

O desenho, em palavras

Região	O que a definição garante
$n < m$	nada. Tudo pode acontecer ali — $g$ pode oscilar, furar o teto, não importa.
$n \ge m$	$g(n)\le c\,f(n)$: $g$ fica sob a curva $c f$, para sempre.

Quando isso acontece, escrevemos $g(n)\in O(f(n))$ — ou, por abuso, $g(n)=O(f(n))$.

Onde está o trabalho: boa parte do esforço de uma prova de complexidade está em determinar as constantes $c$ e $m$. A definição não diz quais são — só exige que existam.

Nota de notação (para quem estuda pelo CLRS)

	Nesta disciplina	CLRS (cap. 3)
Limiar de entrada	$m$	$n_0$
Definição de $O$	$g(n)\le c f(n),\ \forall n\ge m$	$0\le f(n)\le c\,g(n),\ \forall n\ge n_0$
Papel das letras	$g$ = algoritmo, $f$ = teto	$f$ = algoritmo, $g$ = teto

É a mesma definição — só mudam os nomes das letras. O CLRS ainda exige $g(n)\ge 0$ (funções assintoticamente não negativas), o que é natural para funções de custo.

Abuso de notaçãoEscrevemos $g(n)=O(f(n))$, mas o rigoroso seria $g(n)\in O(f(n))$: $O(f(n))$ é um conjunto. O abuso é universal na literatura, e tem vantagens — mas lembre do significado real.

A2 · 06

Exemplos de $O$

Provar “$g\in O(f)$” é sempre a mesma receita: exibir um par $(c,m)$ e verificar a desigualdade para todo $n\ge m$.

Exemplo 1 · $g(n)=2n$ pertence a $O(n)$?

Precisamos exibir constantes $c,m>0$ tais que $2n\le c\cdot n$ para todo $n\ge m$.

Solução. Tome $c=2$ e $m=1$:

$$2n \le 2n \quad \text{para todo } n\ge 1 \qquad \checkmark\ \text{(trivialmente verdadeiro)}$$ $$\therefore\; g(n)=2n=O(n)$$

A constante $c$ “absorveu” o fator 2. É exatamente assim que a notação ignora constantes multiplicativas.

Exemplo 2 · $g(n)=n$ pertence a $O(n^2)$?

Solução. Tome $c=1$ e $m=1$:

$$n \le n^2 \quad \text{para todo } n\ge 1 \qquad (\text{divida os dois lados por } n:\ 1\le n)\ \checkmark$$ $$\therefore\; n=O(n^2)$$

O teto não precisa ser justo$n$ também é $O(n)$, o que é uma afirmação mais forte. Dizer $n=O(n^2)$ é verdadeiro — apenas menos informativo. É como dizer “tenho no máximo 200 anos”.

Exemplo 3 (CLRS) · toda função linear está em $O(n^2)$

Mostrar que $g(n)=an+b$, com $a>0$, pertence a $O(n^2)$.

Solução. Tome $c=a+|b|$ e $m=1$. Para todo $n\ge 1$:

$$an+b \;\le\; an+|b| \qquad (\text{pois } b\le|b|)$$ $$\le\; an^2+|b|\,n^2 \qquad (\text{pois } n\le n^2 \text{ e } 1\le n^2)$$ $$=\; (a+|b|)\,n^2 \;=\; c\,n^2 \qquad \checkmark$$ $$\therefore\; an+b=O(n^2)$$

Por que este exemplo importa. As constantes nem sempre são óbvias: aqui $c$ depende de $a$ e de $b$. A definição só pede que exista alguma escolha válida.

A2 · 07

Exemplo 4 · provando que $n^2\notin O(n)$

O enunciado do slide é uma armadilha proposital: “mostre que $g(n)=n^2$ pertence a $O(n)$… ou mostre que isso é falso”.

Intuição antes da prova

Plotando $n^2$ contra as retas $5n$ e $7n$: a parábola cruza $5n$ em $n=5$ e cruza $7n$ em $n=7$. Qualquer reta $c\cdot n$ é ultrapassada por $n^2$ em algum ponto, justamente $n=c$. Aumentar $c$ só adia o cruzamento.

Prova por contradição

Afirmação. Falso: $n^2$ não pertence a $O(n)$.

Suponha que existam constantes $c,m>0$ tais que $n^2\le c\,n$ para todo $n\ge m$.
Dividindo os dois lados por $n$ (com $n>0$): $n\le c$ para todo $n\ge m$.
Mas $c$ é uma constante fixa e $n$ cresce sem limite: basta tomar $n=\max(m,\lceil c\rceil+1)$ para violar a desigualdade.
Contradição. Tais constantes não existem. $\blacksquare$

Moral. Nenhum múltiplo constante de $n$ segura $n^2$: são formas de crescimento diferentes. É por isso que a notação captura a “forma” da função, e não o tamanho dela num ponto.

A2 · 08

Notação $\Omega$ — o piso

Definição

$O$ dá um teto: “$g$ não cresce mais que $f$”. $\Omega$ dá um piso: “$g$ cresce pelo menos como $f$”.

$$\Omega(f(n)) := \{\, g(n) \;:\; \exists\, c,m>0 \ \text{t.q.}\ g(n)\ge c\,f(n),\ \forall\, n\ge m \,\}$$

É a definição de $O$ com a desigualdade invertida: $\ge$ no lugar de $\le$. Depois de $m$, $g$ fica acima de $cf$, para sempre.

Simetria transposta (CLRS, p. 52) $$g(n)=O(f(n)) \iff f(n)=\Omega(g(n))$$

Exemplo: $n=O(n^2) \iff n^2=\Omega(n)$. Teto de um lado, piso do outro — é a mesma desigualdade lida de dois pontos de vista.

Exemplo · $g(n)=3n^3+n^2$ pertence a $\Omega(n^3)$?

Precisamos exibir constantes $c,m>0$ tais que $3n^3+n^2\ge c\,n^3$ para todo $n\ge m$.

Solução. Tome $c=1$ e $m=1$:

$$3n^3+n^2 \ge n^3 \qquad (\text{queremos mostrar isso})$$ $$2n^3+n^2 \ge 0 \qquad (\text{subtraindo } n^3 \text{ de ambos os lados})$$ $$\text{verdadeiro para todo } n\ge 1 \qquad \checkmark$$ $$\therefore\; 3n^3+n^2=\Omega(n^3)$$

De fato, poderíamos ter tomado até $c=3$: $3n^3+n^2\ge 3n^3$ vale para todo $n\ge 1$. Várias escolhas funcionam — basta uma.

Uso típico. $\Omega$ é a notação dos limites inferiores: “qualquer algoritmo de comparação para ordenar precisa de $\Omega(n\log n)$ comparações”. É uma afirmação sobre o problema, não sobre um algoritmo específico.

A2 · 09

Notação $\Theta$ — o sanduíche

Definição

E se a mesma função $f$ servir de teto e piso ao mesmo tempo (com constantes diferentes)? Então $g$ cresce exatamente como $f$: mesma ordem de crescimento.

$$\Theta(f(n)) := \{\, g(n) \;:\; \exists\, c_1,c_2,m>0 \ \text{t.q.}\ c_1f(n)\le g(n)\le c_2f(n),\ \forall\, n\ge m \,\}$$

$g$ fica imprensada (“sanduíche”) entre dois múltiplos de $f$. O CLRS chama $f$ de limite assintoticamente justo (asymptotically tight bound) para $g$.

Peça	Papel
$c_2f(n)$	teto — é a parte $O$
$c_1f(n)$	piso — é a parte $\Omega$
depois de $m$	$g$ vive dentro da faixa: ordem de crescimento exata

A2 · 10

$n^2+400n=\Theta(n^2)$ — piso, teto e o truque do max

Estratégia: duas desigualdades, uma de cada vez

Piso: achar $c_1,m_1$ com $c_1n^2\le n^2+400n$ para todo $n\ge m_1$.
Teto: achar $c_2,m_2$ com $n^2+400n\le c_2n^2$ para todo $n\ge m_2$.
Combinar: fazer as duas valerem ao mesmo tempo.

Intuição antes da conta: para $n$ grande, $400n$ é minúsculo perto de $n^2$ — em $n=400$ eles empatam, e depois disso $n^2$ dispara. Então $g$ deve se comportar como $n^2$.

Piso · $c_1=1$, $m_1=1$ $$n^2 \le n^2+400n \qquad (\text{subtraia } n^2:\ 0\le 400n) \qquad \checkmark\ \forall n\ge 1$$

Teto · $c_2=2$, $m_2=400$ $$n^2+400n \le 2n^2 \qquad (\text{subtraia } n^2:\ 400n\le n^2,\ \text{i.e., } 400\le n)$$ $$\checkmark\ \forall n\ge 400$$

Observe que cada desigualdade tem seu próprio limiar: $m_1=1$ e $m_2=400$. Falta juntar as duas.

Combinando · o truque padrão

Tome $m=\max(m_1,m_2)$: a partir daí, ambas valem. Com $c_1=1$, $c_2=2$ e $m=\max(1,400)=400$:

$$n^2 \;\le\; n^2+400n \;\le\; 2n^2, \qquad \forall\, n\ge 400$$ $$\therefore\; n^2+400n=\Theta(n^2)$$

O $\max$ volta em praticamente toda prova que junta duas condições assintóticas — inclusive na prova do Teorema 3.1. Guarde o truque.

A2 · 11

Exemplo do CLRS · $\tfrac12 n^2-3n=\Theta(n^2)$

Mesmo com coeficiente fracionário e termo negativo (CLRS, p. 46), a receita é a mesma. Precisamos de $c_1,c_2,n_0$ com

$$c_1n^2 \;\le\; \tfrac12 n^2-3n \;\le\; c_2n^2, \qquad \forall\, n\ge n_0$$

A conta

Dividindo tudo por $n^2$ — o passo que simplifica o problema inteiro:

$$c_1 \;\le\; \frac12-\frac{3}{n} \;\le\; c_2$$

Direita (teto): $\frac12-\frac{3}{n}\le\frac12$ sempre, porque estamos subtraindo algo positivo. Basta $c_2=\frac12$. $\checkmark$

Esquerda (piso): para $n\ge 7$,

$$\frac12-\frac{3}{n} \;\ge\; \frac12-\frac{3}{7} \;=\; \frac{1}{14}$$

Basta $c_1=\frac{1}{14}$. $\checkmark$

Com $c_1=\frac{1}{14}$, $c_2=\frac12$ e $n_0=7$:

$$\tfrac12 n^2-3n=\Theta(n^2)$$

LiçãoAs constantes podem ser fracionárias e nada óbvias. Não importa: a definição só exige que alguma escolha exista.

A2 · 12

Teorema 3.1 — amarrando as três notações

Teorema (CLRS, Teorema 3.1)

Sejam $f(n)$ e $g(n)$ funções. Então:

$$g(n)=\Theta(f(n)) \iff g(n)=O(f(n))\ \text{ e }\ g(n)=\Omega(f(n))$$

A intuição é imediata: sanduíche = teto + piso.
A prova é um ótimo exercício de fixação: junte as constantes das duas definições (de novo o truque do $\max$).
Uso prático: para provar $\Theta$, prove $O$ e $\Omega$ separadamente — é quase sempre mais fácil. Foi exatamente o que fizemos com $n^2+400n$.

Θ é mais forte que O$g=\Theta(f)$ implica $g=O(f)$, mas a recíproca é falsa: em conjuntos, $\Theta(f(n))\subseteq O(f(n))$. Contraexemplo: $n=O(n^2)$, mas $n\neq\Theta(n^2)$.

A2 · 13

Estudo de caso: ordenação por inserção

Insertion sortpior caso $\Theta(n^2)$

para j = 2 ate n:
chave = A[j]
i = j - 1
enquanto i > 0 e A[i] > chave:
A[i+1] = A[i]
i = i - 1
A[i+1] = chave

Pior caso · vetor em ordem decrescente

O laço interno executa $j-1$ vezes:

$$\sum_{j=2}^{n}(j-1)=\frac{n(n-1)}{2}$$

Custo $\Theta(n^2)$.

Melhor caso · vetor já ordenado

O laço interno nunca executa: a condição $A[i]>\text{chave}$ falha de cara.

Custo $\Theta(n)$.

O que podemos afirmar sobre o tempo de execução (sem fixar a entrada)

Afirmação	Vale?	Por quê
É $O(n^2)$	sim	nenhuma entrada custa mais que $c\,n^2$
É $\Omega(n)$	sim	toda entrada custa pelo menos $c\,n$
É $\Theta(n^2)$	não	existe entrada (já ordenada) em que o custo é $\Theta(n)$, quebrando o piso $c_1n^2$

Cuidado com o equívoco clássico$O$ não significa “pior caso” e $\Omega$ não significa “melhor caso”. As notações limitam funções, não casos. É correto dizer: o pior caso é $\Theta(n^2)$; o melhor caso é $\Theta(n)$; o tempo de execução é $O(n^2)$ e $\Omega(n)$.

A2 · 14

Checkpoint · teste você mesmo

Seja $g(n)=5n^2+100$. Quais afirmações são verdadeiras?

#	Afirmação	V/F	Justificativa
1	$g(n)=O(n^2)$	V	$c=6,\ m=10$: $5n^2+100\le 6n^2 \iff 100\le n^2$
2	$g(n)=O(n^3)$	V	teto não precisa ser justo
3	$g(n)=\Omega(n^2)$	V	$c=5,\ m=1$
4	$g(n)=\Theta(n^3)$	F	falha o piso: $c_1n^3\le 5n^2+100$ é impossível para $n$ grande
5	$g(n)=\Theta(n^2)$	V	itens 1 e 3 + Teorema 3.1

Se acertou as cinco, você entendeu as três notações.

A2 · 15

O, Ω e Θ são famílias de conjuntos

Primeiro slide da Parte 5, e o único dela que a aula abriu. Ele fecha a conta pendente desde a definição de $O$: por que escrevemos $=$ onde o certo seria $\in$.

O que essas notações são, de verdade

Para cada $f$, $O(f(n))$ é um conjunto de funções — logo $O$, $\Omega$ e $\Theta$ são famílias de conjuntos.
Os operadores formalmente corretos seriam os de conjuntos: $g\in O(f)$, $\Theta(f)\subseteq O(f)$, e assim por diante.
Na prática, abusamos da notação com símbolos aritméticos.

Escrevemos · queremos dizer

Escrevemos	Queremos dizer
$2n=O(n)$	$2n\in O(n)$
$T(n)=2T(n/2)+\Theta(n)$	$T(n)=2T(n/2)+h(n)$ para alguma $h\in\Theta(n)$
$n^2+O(n)=O(n^2)$	para toda escolha à esquerda, a igualdade vale

O abuso é útil: elimina detalhes sem importância das equações (CLRS, p. 49–50). Mas lembre-se sempre do significado real — as três linhas acima querem dizer coisas diferentes, mesmo usando o mesmo sinal de igual.

A segunda linha, com $T(n)=2T(n/2)+\Theta(n)$, é uma recorrência: essa forma volta na próxima aula, na análise de algoritmos recursivos.

A2 · 16

Classes de comportamento assintótico

A notação $O$ dá uma família infinita de conjuntos, mas alguns aparecem o tempo todo na análise de algoritmos. São as classes de comportamento assintótico, e a aula as apresentou de uma vez, numa única linha de custo crescente.

A hierarquia, em ordem de custo crescente $$O(1) \subset O(\log n) \subset O(n) \subset O(n\log n)$$ $$\subset\; O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n!)$$

Da esquerda para a direita, o custo cresce. Saber essa ordem de cor é o que resolve a questão típica de prova: “ordene estas funções por ordem de crescimento”.

A aula não abriu os slides de cada classe uma a uma — parou nesta linha e desenvolveu duas delas, $O(n^2)$ e $O(2^n)$, no tópico seguinte. As duas não foram escolhidas ao acaso: elas são exatamente os dois lados da fronteira que fecha a aula.

A2 · 17

Polinomial × exponencial

Definições

Algoritmo polinomial: tempo $O(p(n))$ para algum polinômio $p(n)$ — ex.: $n$, $n\log n$, $n^2$, $n^{10}$.
Algoritmo exponencial: tempo de ordem maior que qualquer polinômio — ex.: $c^n$ com $c>1$, $n!$.

Algoritmos exponenciais são, em geral, variações de busca exaustiva: testar tudo. Algoritmos polinomiais costumam exigir um entendimento mais profundo da estrutura do problema.

As duas classes que a aula desenvolveu servem de representante de cada lado da fronteira.

O lado polinomial · $O(n^2)$

A assinatura: elementos processados aos pares — na prática, dois laços aninhados. Um laço de $n$ iterações dentro de outro de $n$ iterações executa o corpo $n\cdot n=n^2$ vezes.

Sensibilidade: dobrou a entrada $\Rightarrow$ tempo multiplicado por 4.

Exemplos:

percorrer uma matriz $n\times n$;
ordenação por seleção — e por inserção, no pior caso (o estudo de caso do tópico 13);
maior subsequência comum (LCS) por programação dinâmica.

O lado exponencial · $O(2^n)$

A assinatura: testar todas as escolhas binárias sobre $n$ elementos. A escolha típica é “este elemento está ou não está na minha solução?”, repetida $n$ vezes — o que dá $2^n$ combinações a testar:

$$\underbrace{2\times 2\times\cdots\times 2}_{n\ \text{elementos}} = 2^n$$

Sensibilidade: adicionar um elemento à entrada dobra o tempo. Compare com $O(n^2)$, onde ir de $n$ para $n+1$ quase não muda nada — é aí que está a diferença real entre os dois lados.

Exemplos:

satisfabilidade booleana (SAT);
mochila 0/1 por força bruta; subset sum; partição;
conjunto independente máximo.

A força bruta é o ponto de partida; o insight estrutural é o que derruba a classe de complexidade.

A2 · 18

Problemas bem resolvidos e problemas intratáveis

A distinção polinomial × exponencial se torna decisiva quando o tamanho do problema cresce. Dizemos que um problema é:

Bem resolvido

Existe algoritmo polinomial que o resolve.

Ordenação, busca, caminhos mínimos, …

Intratável

Não se conhece algoritmo polinomial que o resolva.

Caixeiro viajante, SAT, mochila 0/1, …

Repare que os exemplos de intratável são os mesmos do tópico anterior: são justamente os problemas que só sabemos atacar por busca exaustiva.

P vs. NP, em duas linhas

“Não se conhece” $\neq$ “não existe”: para muitos desses problemas, ninguém provou impossibilidade…
…essa é exatamente a questão P vs. NP, um dos problemas em aberto mais famosos da computação. Vocês a verão formalmente em disciplinas futuras.

Cuidado com a palavra “intratável”Ela descreve o estado do conhecimento, não uma impossibilidade provada. Escrever “é impossível resolver o caixeiro viajante em tempo polinomial” é afirmar $P\neq NP$ — coisa que ninguém provou. O enunciado correto é “não se conhece algoritmo polinomial”.

A2 · Extra

Como provar que não é $O$, $\Omega$ ou $\Theta$

Fora do slide. A aula prova uma única negativa — $n^2\notin O(n)$, no Exemplo 4 — e usa a negativa no checkpoint (item 4) e no insertion sort sem repetir o método. Esta seção generaliza o que já está lá.

A ideia em uma linha

As três definições são da forma “existem constantes tais que a desigualdade vale para todo $n\ge m$”. Negar isso é trocar os quantificadores:

$$\exists\, c,m \ \text{t.q.}\ \forall\, n\ge m \quad\longrightarrow\quad \forall\, c,m \ \exists\, n\ge m \ \text{que viola}$$

Ou seja: não basta mostrar que a sua escolha de $c$ falhou. É preciso mostrar que nenhuma escolha funciona — por isso a prova quase sempre é por contradição.

O roteiro, nos três casos

Provar que…	Suponha que existam…	E derive a contradição
$g\notin O(f)$	$c,m>0$ com $g(n)\le c f(n)$, $\forall n\ge m$	isole $c$: $\frac{g(n)}{f(n)}\le c$. Se o quociente cresce sem limite, algum $n$ ultrapassa $c$.
$g\notin \Omega(f)$	$c,m>0$ com $g(n)\ge c f(n)$, $\forall n\ge m$	isole $c$: $\frac{g(n)}{f(n)}\ge c$. Se o quociente tende a zero, algum $n$ fica abaixo de $c$.
$g\notin \Theta(f)$	—	pelo Teorema 3.1, basta derrubar um dos lados: mostre $g\notin O(f)$ ou $g\notin\Omega(f)$.

Modelo 1 · negando $O$ — o Exemplo 4 da aula

Provar $n^2\notin O(n)$:

Suponha $c,m>0$ com $n^2\le c\,n$ para todo $n\ge m$.
Divida por $n>0$: $n\le c$ para todo $n\ge m$.
Exiba o $n$ que quebra: $n=\max(m,\lceil c\rceil+1)$ satisfaz $n\ge m$ e $n>c$.
Contradição. $\blacksquare$

O passo 3 é o coração: como $c$ e $m$ eram arbitrários, o contraexemplo é construído em função deles — e por isso vale para todos.

Modelo 2 · negando $\Omega$

Provar $n\notin\Omega(n^2)$:

Suponha $c,m>0$ com $n\ge c\,n^2$ para todo $n\ge m$.
Divida por $n>0$: $1\ge c\,n$, ou seja, $n\le 1/c$ para todo $n\ge m$.
Tome $n=\max(m,\lceil 1/c\rceil+1)$: ele é $\ge m$ e maior que $1/c$.
Contradição. $\blacksquare$

Note a simetria transposta em ação: isso é o mesmo fato que $n^2\notin O(n)$, lido do outro lado.

Modelo 3 · negando $\Theta$ — o item 4 do checkpoint

Provar $5n^2+100\notin\Theta(n^3)$. Pelo Teorema 3.1, basta derrubar o piso:

Suponha $c_1,m>0$ com $c_1n^3\le 5n^2+100$ para todo $n\ge m$.
Para $n\ge 1$ vale $100\le 100n^2$, logo $5n^2+100\le 105n^2$; então $c_1n^3\le 105n^2$.
Divida por $n^2>0$: $n\le 105/c_1$ para todo $n\ge m$ — de novo um $n$ ilimitado preso abaixo de uma constante.
Tome $n=\max(m,1,\lceil 105/c_1\rceil+1)$. Contradição. $\blacksquare$

O teto $5n^2+100=O(n^3)$ continua verdadeiro — é só o piso que falha. Por isso a resposta é “$O$ sim, $\Theta$ não”.

Erro que custa a questãoEscrever “testei $c=5$ e não deu, logo não é $O$” não prova nada: a definição pede que exista alguma constante, e sempre haveria outra a testar. A prova só fecha quando o $n$ que viola é construído a partir de $c$ e $m$ genéricos — exatamente como no $\max(m,\lceil c\rceil+1)$.

Revisão

Checklist da A2

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

Pergunta	Onde está
Explicar por que o algoritmo de menor ordem vence hardware 1000× mais rápido	Por que a ordem de crescimento importa
Dizer o que a análise assintótica descarta, e por quê	O que a assintótica joga fora
Escrever as definições de $O$, $\Omega$ e $\Theta$ com os quantificadores certos	Notação $O$ · $\Omega$ · $\Theta$
Exibir $c$ e $m$ para provar $an+b=O(n^2)$	Exemplos de $O$
Provar por contradição que $n^2\notin O(n)$	Provando que $n^2\notin O(n)$
Provar $\Theta$ em duas etapas e juntar com $m=\max(m_1,m_2)$	Θ na prática
Enunciar o Teorema 3.1 e usá-lo para reduzir uma prova de $\Theta$	Teorema 3.1
Dizer o pior caso, o melhor caso e o tempo de execução do insertion sort — cada um com a notação correta	Estudo de caso
Traduzir $g(n)=O(f(n))$ para a linguagem de conjuntos, e dizer o que o sinal de igual esconde	Famílias de conjuntos
Ordenar as classes de $O(1)$ a $O(n!)$ por custo crescente	Classes de comportamento assintótico
Separar algoritmo polinomial de exponencial e dar a assinatura de cada um	Polinomial × exponencial
Explicar por que “intratável” não quer dizer “impossível”	Bem resolvidos × intratáveis
Montar a negação de $O$, $\Omega$ e $\Theta$ e exibir o $n$ que viola	Extra · como provar que não é

A2 · Cobertura

Como esta aula foi dada — o mapa dos pulos

A aula não correu em linha reta pelo PDF. Até a página 165 ela seguiu a ordem dos slides. Da 166 em diante o professor saltou: abriu só o primeiro slide da Parte 5, pulou as propriedades inteiras, voltou na Parte 6 apenas para a linha das classes, desenvolveu uma delas e fechou com os dois últimos slides da parte. Este resumo cobre exatamente o que foi dado — nada além.

O que ele deu · e onde está aqui

Páginas	Assunto	Tópico
1–165	Motivação, notações $O$, $\Omega$ e $\Theta$, Teorema 3.1, insertion sort e checkpoint	01–14
167–173	$O$, $\Omega$ e $\Theta$ como famílias de conjuntos, com a tabela “escrevemos / queremos dizer”	15
200–209	A linha das classes, de $O(1)$ a $O(n!)$	16
242–245 · 249–252	$O(n^2)$ e $O(2^n)$ — as duas classes desenvolvidas	17
268–272	Polinomial × exponencial	17
273–277	Problemas bem resolvidos × intratáveis, e o P vs. NP	18

O que ele pulou · não caiu nesta aula

Páginas	Assunto
174–198	Propriedades da notação — regras da soma e do produto, transitividade, reflexividade, simetria, a analogia com os números reais e a falha da tricotomia
210–241 · 246–248 · 253–255	As outras seis classes, uma a uma: $O(1)$, $O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^3)$ e $O(n!)$
256–260	Bogosort e a hierarquia infinita de classes
261–267	A tabela de tempo de relógio para $n=20,40,60$
278–282	Desempate entre dois algoritmos da mesma classe
283–298	Resumo da aula, lista de exercícios e referências

Se algum desses trechos for cobrado depois, ele entra como bloco novo — não está aqui porque não foi dado.

A seção Extra sobre negar $O$, $\Omega$ e $\Theta$ é acréscimo meu, fora do slide, e está marcada como tal.

Região	O que a definição garante
\(n < m\)	nada. Tudo pode acontecer ali — \(g\) pode oscilar, furar o teto, não importa.
\(n \ge m\)	\(g(n)\le c\,f(n)\): \(g\) fica sob a curva \(c f\), para sempre.

	Nesta disciplina	CLRS (cap. 3)
Limiar de entrada	\(m\)	\(n_0\)
Definição de \(O\)	\(g(n)\le c f(n),\ \forall n\ge m\)	\(0\le f(n)\le c\,g(n),\ \forall n\ge n_0\)
Papel das letras	\(g\) = algoritmo, \(f\) = teto	\(f\) = algoritmo, \(g\) = teto

Peça	Papel
\(c_2f(n)\)	teto — é a parte \(O\)
\(c_1f(n)\)	piso — é a parte \(\Omega\)
depois de \(m\)	\(g\) vive dentro da faixa: ordem de crescimento exata

#	Afirmação	V/F	Justificativa
1	\(g(n)=O(n^2)\)	V	\(c=6,\ m=10\): \(5n^2+100\le 6n^2 \iff 100\le n^2\)
2	\(g(n)=O(n^3)\)	V	teto não precisa ser justo
3	\(g(n)=\Omega(n^2)\)	V	\(c=5,\ m=1\)
4	\(g(n)=\Theta(n^3)\)	F	falha o piso: \(c_1n^3\le 5n^2+100\) é impossível para \(n\) grande
5	\(g(n)=\Theta(n^2)\)	V	itens 1 e 3 + Teorema 3.1

Escrevemos	Queremos dizer
\(2n=O(n)\)	\(2n\in O(n)\)
\(T(n)=2T(n/2)+\Theta(n)\)	\(T(n)=2T(n/2)+h(n)\) para alguma \(h\in\Theta(n)\)
\(n^2+O(n)=O(n^2)\)	para toda escolha à esquerda, a igualdade vale

Complexidadeassintótica

Por que a ordem de crescimento importa

O que a assintótica joga fora

Observação 1 — termos que não dependem de \(n\)

Observação 2 — a constante que multiplica \(n\)

Formas de crescimento diferentes

A estratégia: três conjuntos de funções

Notação \(O\) — o teto

O desenho, em palavras

Nota de notação (para quem estuda pelo CLRS)

Exemplos de \(O\)

Exemplo 4 · provando que \(n^2\notin O(n)\)

Notação \(\Omega\) — o piso

Notação \(\Theta\) — o sanduíche

\(n^2+400n=\Theta(n^2)\) — piso, teto e o truque do max

Exemplo do CLRS · \(\tfrac12 n^2-3n=\Theta(n^2)\)