Notação Big-O

Conceito

Big-O não mede tempo e não conta operações. Mede como o custo cresce quando a entrada cresce — é uma cota superior assintótica sobre a taxa de crescimento.

Por que assintótico: constantes e termos menores dependem de hardware, compilador, cache e clima. O que sobrevive a todas essas variações é a forma da curva. Big-O isola o que é do algoritmo do que é da máquina.

O(2n) e O(n) são a mesma classe porque a definição descarta constante multiplicativa — de propósito. A constante volta a importar em dois casos: quando n é pequeno (quase sempre, na prática) e quando a constante é absurda (existem algoritmos de multiplicação de matrizes com expoente melhor e constante que os torna inúteis para qualquer n real).

As três medidas, e a diferença que importa:

O termo "amortizado" vem da contabilidade: amortizar é distribuir um custo concentrado ao longo de um período. Você compra uma máquina de R$ 12.000 que dura 12 meses e lança R$ 1.000/mês — o gasto foi real e concentrado, mas diluído no período é constante.

append é idêntico: copiar 8 elementos no append #8 foi real e caro, e só aconteceu porque os appends #4 a #7 foram de graça. Diluído entre eles, o custo é constante.

A confusão entre "médio" e "amortizado" é a mais comum, e a diferença é a natureza da promessa:

• caso médio é uma aposta na distribuição da entrada — um adversário pode escolher a entrada que quebra a suposição
• amortizado não supõe nada — não existe sequência de entrada que faça N appends custarem mais que O(N), porque a conta já somou todas as operações caras

O par de comparação: m[k] num mapa é O(1) esperado (caso médio), e é exatamente por isso que Go randomiza a semente do hash — para impedir que alguém escolha chaves colidentes e destrua a suposição (7. Tratamento de Colisão). append é O(1) amortizado, e nenhuma entrada quebra isso.

E "constante" não quer dizer "sempre o mesmo número", quer dizer "não cresce com n":

n cresceu um milhão de vezes; o custo por operação convergiu para ~5. É isso.

O que Big-O esconde: memória, localidade de cache, I/O, e a constante. Um O(n log n) que percorre memória sequencialmente frequentemente vence um O(n) que salta aleatoriamente — porque um cache miss custa duas ordens de magnitude mais que uma comparação.

O é cota superior, Ω inferior, Θ as duas. Dizer "busca linear é O(n²)" é tecnicamente verdadeiro e completamente inútil — por isso na prática todo mundo diz O querendo dizer Θ.

Em Go

Go te dá medição empírica de primeira classe, o que é o antídoto certo para a teoria — go test -bench . -benchmem:

func BenchmarkBuscaLinear(b *testing.B) {
	for i := 0; i < b.N; i++ { buscaLinear(dados, alvo) }
}

b.N é ajustado pelo runtime até a medição estabilizar. -benchmem acrescenta allocs/op, que frequentemente explica mais que a complexidade.

Complexidade das operações da stdlib que vale ter memorizada:

A constante que faz append ser amortizado O(1) em Go: até 256 elementos a capacidade dobra; acima disso o incremento é cap/4 + 192 elementos, depois arredondado para a classe de tamanho do alocador (Go 1.18+). Esse +192 importa: o fator só converge para 1,25× em capacidades grandes.

Por que geométrico dá O(1) amortizado

A contradição aparente: um append pode custar O(n) (realocar e copiar tudo). Então como ele é O(1)?

Porque o caro fica raro na mesma velocidade em que fica caro. Com fator 2, as realocações ocorrem em cap = 1, 2, 4, 8, … e cada uma copia o cap anterior:

1 + 2 + 4 + 8 + ... + n/2  ≈  n

Série geométrica: o custo dobra, a frequência cai pela metade, e os dois se cancelam. Você paga ~1 cópia por elemento — distribuída de forma desigual, limitada no total.

Medido, contando cada elemento copiado em 100.000 appends:

A última linha do meio é a que prova a tese: aditivo copia 1+2+...+n = n²/2, ou seja n/2 por append — O(n) amortizado, 5 bilhões de cópias em vez de 130 mil.

O número de cópias por append fica entre 1/(k-1) e k/(k-1). Confira: k=1,01 prevê ~100, mediu 101,11.

E o fator é um botão entre cópia e memória desperdiçada. Logo após crescer para cap = k·n com n elementos, o desperdício é (k-1)/k:

É por isso que Go muda de política em 256: 50% de desperdício em 100 elementos são 400 bytes — irrelevante, então vale dobrar e copiar menos. 50% em 10 milhões são 40 MB de RAM parada. Go troca cópia por memória exatamente onde a memória passa a importar.

O +192 é um piso. Sem ele, em cap=257 o incremento seria 64 elementos e você realocaria quase de imediato. É também o que explica o fator ~2× observado perto de cap 300: ali o +192 é 64% do próprio cap. Ele só se dilui, e o fator só converge para 1,25×, quando cap ≫ 192.

Somando o arredondamento para classe de tamanho do alocador, o Go real (26 realocações) sai melhor que 1,25× puro (52) — a capacidade extra do arredondamento vem de graça.

A consequência prática: toda essa maquinaria existe para quando você não sabe o tamanho final. Quando sabe, make([]T, 0, n) elimina a conta inteira — zero realocações, zero cópias. Não é economizar 20%: é remover o problema.

Respostas às perguntas-guia

1. O que Big-O mede — tempo, operações, ou crescimento?

Conceito: crescimento. É uma afirmação sobre a função que relaciona tamanho da entrada e custo, não sobre um número.

Em Go: para o número você usa go test -bench; Big-O te diz se vale a pena medir.

2. Por que O(2n) e O(n) são a mesma coisa, e quando a constante importa na prática?

Conceito: a definição descarta constantes porque elas são propriedade da máquina, não do algoritmo. Importa quando n é pequeno ou a constante é gigante.

Em Go, a constante aparece principalmente como alocação: um algoritmo O(n) que aloca por elemento perde de um O(n log n) que não aloca. allocs/op no benchmark é onde isso fica visível.

3. Qual a diferença entre pior caso, caso médio e amortizado?

Conceito: pior caso é garantia por operação; amortizado é garantia por sequência; caso médio é uma aposta na distribuição da entrada.

Em Go: append e o map são amortizados. append individual pode realocar e copiar tudo; a sequência de N appends custa O(N).

4. Você consegue estimar a complexidade de uma função sua sem contar linha por linha?

Conceito: o atalho é olhar estrutura de repetição e o que ela percorre: laços aninhados sobre a mesma coleção → n²; divisão do problema pela metade → log n; laço que percorre uma vez → n; laço com trabalho log n dentro → n log n.

Em Go, a armadilha é que a chamada esconde o laço: slices.Contains dentro de um for te dá O(n²) sem nenhum laço aninhado visível. É o bug de performance mais comum — e a correção quase sempre é trocar por map.

Trade-offs

Do conceito:

• Análise assintótica é portátil entre máquinas e inútil para escolher entre dois O(n). Aí só medição resolve.
• Otimizar a classe de complexidade é a única otimização que escala; otimizar a constante é a única que ajuda quando n já é pequeno.
• Pior caso é honesto e pessimista; caso médio é otimista e frágil.

Em Go: benchmark é fácil e por isso a tentação é medir sem pensar. Medir um caso de tamanho errado te dá a resposta certa para a pergunta errada — varie o n.

Exemplo prático

O cruzamento entre O(n) e O(1), que é o argumento inteiro da semana:

package main

import (
	"fmt"
	"slices"
	"time"
)

func main() {
	for _, n := range []int{100, 10_000, 1_000_000} {
		dados := make([]int, n)
		for i := range dados {
			dados[i] = i
		}
		indice := make(map[int]bool, n)
		for _, v := range dados {
			indice[v] = true
		}
		alvo := n - 1 // pior caso da busca linear

		t := time.Now()
		for i := 0; i < 1000; i++ {
			_ = slices.Contains(dados, alvo) // O(n)
		}
		linear := time.Since(t)

		t = time.Now()
		for i := 0; i < 1000; i++ {
			_ = indice[alvo] // O(1)
		}
		hash := time.Since(t)

		fmt.Printf("n=%-9d linear=%-12v hash=%-10v razao=%.0fx\n",
			n, linear, hash, float64(linear)/float64(hash))
	}
}

Saída real desta máquina:

n=100       linear=74.973µs     hash=14.166µs   razao=5x
n=10000     linear=6.328854ms   hash=17.172µs   razao=369x
n=1000000   linear=578.082725ms hash=16.123µs   razao=35855x

Repare nas duas colunas. O tempo do hash é praticamente constante — é o O(1). O da busca linear acompanha n — é o O(n). E a razão cresce sem limite: é isso que a notação está dizendo. Com n=100 o tempo absoluto é irrelevante nos dois casos; a mesma linha de código passa de 75µs para meio segundo sem ninguém ter mudado nada além do tamanho dos dados.

Relacionado

• 2. Array e 3. Lista Ligada — mesma interface, complexidades opostas
• 6. Hash Map — o O(1) que motiva a estrutura toda
• 1. Busca Binária — de onde vem o log n
• 7. Problema N+1 — semana 9, O(n) escondido atrás de uma chamada

---

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação