Big O não é matemática académica — é a linguagem com que raciocinas sobre o que acontece à performance do teu código quando os dados crescem de 100 para 1 milhão de registos. A diferença entre uma query que demora 2ms e uma que demora 45 segundos na mesma tabela é quase sempre uma questão de complexidade algorítmica: um índice ausente, uma estrutura de dados errada, um loop dentro de um loop. Perceber Big O é perceber porque essas diferenças existem — e como evitá-las por design.
Um algoritmo é uma sequência finita e determinística de passos que transforma um input num output. A mesma computação pode ser feita por algoritmos com eficiências radicalmente diferentes — e a escolha do algoritmo importa muito mais do que a escolha da linguagem ou do hardware.
// O mesmo problema — duas abordagens com eficiências radicalmente diferentes:
// Problema: verificar se um email já existe numa lista de utilizadores
// Abordagem 1 — lista não ordenada, verificação linear
List<String> emails = getAllUserEmails(); // 1 000 000 emails
boolean exists = emails.contains("ana@example.com");
// O Java percorre a lista do início ao fim até encontrar ou esgotar
// Pior caso: percorre todos os 1 000 000 elementos
// Complexidade: O(n) — cresce linearmente com o tamanho da lista
// Abordagem 2 — HashSet, verificação em tempo constante
Set<String> emailSet = new HashSet<>(getAllUserEmails());
boolean exists = emailSet.contains("ana@example.com");
// O Java calcula o hash do email e vai directamente à posição correcta
// Independentemente de ter 100 ou 1 000 000 emails: o mesmo tempo
// Complexidade: O(1) — constante, não cresce com o tamanho
// A diferença na prática com 1 000 000 utilizadores:
// List.contains() → potencialmente 1 000 000 comparações de strings
// HashSet.contains() → potencialmente 1 comparação
//
// Para 10× mais utilizadores (10 000 000):
// List.contains() → potencialmente 10 000 000 comparações (10× mais lento)
// HashSet.contains() → potencialmente 1 comparação (igual)
//
// A escolha da estrutura de dados importa mais do que o hardware.Big O descreve como o tempo de execução (ou uso de memória) de um algoritmo cresce em função do tamanho do input n. Ignora constantes e termos de menor ordem — interessa o comportamento assimptótico: o que acontece quando n é grande.
// As complexidades mais comuns — da melhor para a pior:
// O(1) — Constante
// O tempo não depende do tamanho do input
// Exemplos: acesso a elemento de array por índice, HashMap.get(), HashSet.contains()
int primeiro = array[0]; // sempre 1 operação, independentemente do tamanho do array
map.get("chave"); // sempre ~1 operação (na ausência de colisões de hash)
// O(log n) — Logarítmica
// A cada passo, o problema é dividido a meio
// Exemplos: pesquisa binária, operações em B-tree (índices SQL), TreeMap.get()
// Para n=1 000 000: log₂(1 000 000) ≈ 20 passos
// Para n=1 000 000 000: log₂(1 000 000 000) ≈ 30 passos — cresce muito lentamente
int idx = Arrays.binarySearch(sortedArray, target); // O(log n)
// O(n) — Linear
// O tempo cresce proporcionalmente ao tamanho do input
// Exemplos: percorrer uma lista, List.contains(), soma de todos os elementos
for (int x : list) { sum += x; } // percorre todos os n elementos uma vez
// O(n log n) — Linearítmica
// Melhor que O(n²), pior que O(n)
// Exemplos: os melhores algoritmos de ordenação (mergesort, heapsort, timsort)
Collections.sort(list); // O(n log n) — timsort no Java
// O(n²) — Quadrática
// Para cada elemento, percorre todos os outros — loop dentro de loop
// Com n=10 000: 100 000 000 operações — começa a ser problemático
// Exemplos: bubble sort, algoritmos de comparação ingénuos
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { // para cada i, percorre todos os j
// O(n²) — evitar com inputs grandes
}
}
// O(2ⁿ) — Exponencial
// Duplica a cada elemento adicional — impraticável para n > ~30
// Exemplos: força bruta em criptografia, subconjuntos de um conjunto// Crescimento comparativo — operações para diferentes valores de n:
//
// n O(1) O(log n) O(n) O(n log n) O(n²)
// ─────────────────────────────────────────────────────────────
// 10 1 3 10 33 100
// 100 1 7 100 664 10 000
// 1 000 1 10 1 000 9 966 1 000 000
// 10 000 1 13 10 000 132 877 100 000 000
// 1 000 000 1 20 1 000 000 19 931 569 10¹² (impraticável)
//
// Um algoritmo O(n²) com n=10 000 executa 10 000× mais operações que O(n)
// Um algoritmo O(log n) com n=1 000 000 executa apenas 20 operaçõesA complexidade de uma operação depende directamente da estrutura de dados escolhida. A mesma operação — inserir, procurar, apagar — tem complexidades completamente diferentes em estruturas diferentes.
// Array / ArrayList — elementos contíguos em memória, acesso por índice
ArrayList<String> list = new ArrayList<>();
list.get(i); // O(1) — acesso directo por índice (aritmética de ponteiro)
list.add(x); // O(1) amortizado — pode ser O(n) quando redimensiona o array interno
list.contains(x); // O(n) — percorre do início ao fim
list.remove(i); // O(n) — desloca todos os elementos após i
list.add(0, x); // O(n) — desloca todos os elementos para a direita
// Quando usar: acesso por índice frequente, iteração sequencial, ordem importa
// LinkedList — nós com ponteiros para o próximo (e anterior em doubly-linked)
LinkedList<String> linked = new LinkedList<>();
linked.get(i); // O(n) — percorre desde a cabeça até ao índice i
linked.addFirst(x); // O(1) — apenas actualiza o ponteiro da cabeça
linked.addLast(x); // O(1) — apenas actualiza o ponteiro da cauda
linked.removeFirst(); // O(1)
linked.contains(x); // O(n) — percorre todos os nós
// Quando usar: inserções/remoções frequentes no início ou fim, fila (Queue)
// Na prática: ArrayDeque é quase sempre mais eficiente que LinkedList em Java
// HashMap — tabela de hash, pares chave-valor
HashMap<String, Account> map = new HashMap<>();
map.put("ana@example.com", account); // O(1) amortizado
map.get("ana@example.com"); // O(1) amortizado
map.containsKey("ana@example.com"); // O(1) amortizado
map.remove("ana@example.com"); // O(1) amortizado
// Como funciona internamente:
// 1. Calcula hash da chave: "ana@example.com".hashCode() → 123456789
// 2. hash % array.length → índice do bucket (ex: 42)
// 3. Vai directamente ao bucket 42
// 4. Se houver colisão (duas chaves com o mesmo bucket): lista ligada ou árvore no bucket
//
// Pior caso com muitas colisões: O(n) — mas em prática é O(1) com boa função de hash
// Java 8+: buckets com >8 elementos usam árvore rubro-negra → O(log n) no pior caso
// Quando usar: lookup por chave frequente, verificação de existência, cache simples
// TreeMap — árvore rubro-negra, chaves sempre ordenadas
TreeMap<String, Account> tree = new TreeMap<>();
tree.put("ana@example.com", account); // O(log n)
tree.get("ana@example.com"); // O(log n)
tree.firstKey(); // O(log n) — menor chave
tree.headMap("m@example.com"); // O(log n) — todas as chaves < "m..."
// Quando usar: quando precisas de chaves ordenadas, range queries, min/max eficiente
// Custo: todas as operações são O(log n) em vez de O(1) do HashMapUm índice SQL é uma estrutura de dados separada, mantida pelo motor da base de dados, que permite encontrar linhas sem percorrer a tabela inteira. A estrutura mais usada é a B-tree (e a sua variante B+tree) — que garante O(log n) para pesquisa, inserção e remoção, e O(n) para scan sequencial ordenado.
// Sem índice — full table scan: O(n)
// Para encontrar uma conta com id=42 numa tabela de 1 000 000 linhas:
SELECT * FROM accounts WHERE id = 42;
-- O motor percorre todas as 1 000 000 linhas sequencialmente
-- Para n=10 000 000: 10× mais lento
// Com índice na coluna id — B-tree lookup: O(log n)
CREATE INDEX idx_accounts_id ON accounts(id);
SELECT * FROM accounts WHERE id = 42;
-- O motor desce a B-tree: ~20 comparações para 1 000 000 linhas
-- Para n=10 000 000: ~23 comparações — quase igual
// A estrutura B-tree (simplificada):
//
// [42 | 78 | 156] ← nó raiz
// / | | \
// [12|28|35] [55|61] [90|120] [200|310] ← nós internos
// / | | \
// [5] [15] [30] [40|41|42] ← folhas (contêm os dados ou ponteiros para linhas)
//
// Pesquisa por id=42:
// 1. Raiz: 42 < 42? não. 42 < 78? sim → ramo esquerdo do 78
// 2. Nó [12|28|35]: 42 > 35 → ramo direito
// 3. Folha [40|41|42]: encontrado! → ponteiro para a linha na tabela
// Total: 3 comparações para uma tabela com centenas de linhas no exemplo
// Escala: log₃(1 000 000) ≈ 13 níveis para 1 milhão de registos com nós de 3 chaves
// (B-trees reais têm centenas de chaves por nó — a árvore é muito mais achatada)// Índices compostos — a ordem das colunas importa
// Query do isolamento lógico anti-IDOR:
SELECT * FROM accounts WHERE id = 42 AND owner_id = 99;
// Índice composto (id, owner_id):
CREATE INDEX idx_accounts_id_owner ON accounts(id, owner_id);
-- O B-tree está ordenado por id primeiro, owner_id depois
-- Pesquisa por id=42 AND owner_id=99: O(log n) ✅
-- Pesquisa só por id=42: O(log n) ✅ (usa o prefixo do índice)
-- Pesquisa só por owner_id=99: O(n) ❌ (não pode usar o índice — owner_id não é o prefixo)
// Índice composto (owner_id, id):
CREATE INDEX idx_accounts_owner_id ON accounts(owner_id, id);
-- Pesquisa por owner_id=99 AND id=42: O(log n) ✅
-- Pesquisa só por owner_id=99: O(log n) ✅ (lista todas as contas do utilizador)
-- Pesquisa só por id=42: O(n) ❌
// Regra: o índice é útil quando a query filtra pelo prefixo das colunas do índice
// Para a query anti-IDOR com id e owner_id: ambas as ordens funcionam
// Para listar todas as contas de um utilizador: (owner_id, id) é mais útilOs padrões de complexidade algorítmica aparecem directamente no código de aplicação — muitas vezes disfarçados de código aparentemente inocente.
// ── Padrão 1: O(n²) disfarçado — verificação em loop com query por item ──────
// ❌ O(n²) — para cada conta, faz uma query à base de dados
List<Long> accountIds = getAccountIds(); // n IDs
List<Account> accounts = new ArrayList<>();
for (Long id : accountIds) { // loop: O(n)
accounts.add(repository.findById(id) // query por item: O(log n) cada
.orElseThrow(...)); // total: O(n log n) no melhor caso
} // mas n queries à BD = n × latência de rede
// Para n=1000 contas e 5ms por query → 5 segundos apenas em latência de BD
// ✅ O(n) — uma única query para todos os IDs
List<Account> accounts = repository.findAllById(accountIds);
// Spring Data gera: SELECT * FROM accounts WHERE id IN (1, 2, 3, ..., 1000)
// 1 query, 1 round-trip à BD, O(n) — independentemente de n
// ── Padrão 2: Filtrar em memória vs filtrar na BD ─────────────────────────────
// ❌ Traz tudo para memória, filtra em Java
List<Account> all = repository.findAll(); // SELECT * FROM accounts — todos!
List<Account> active = all.stream()
.filter(a -> a.getOwnerId().equals(userId)) // filtra em memória
.filter(a -> a.getStatus() == AccountStatus.ACTIVE)
.collect(Collectors.toList());
// Com 10 000 000 de contas: traz 10M linhas da BD para a JVM, usa GBs de memória
// ✅ Filtra na BD — apenas os dados necessários atravessam a rede
List<Account> active = repository
.findByOwnerIdAndStatus(userId, AccountStatus.ACTIVE);
// SELECT * FROM accounts WHERE owner_id = 99 AND status = 'ACTIVE'
// Com índice em (owner_id, status): O(log n + k) onde k = número de resultados
// ── Padrão 3: Duplicar dados para O(1) em vez de O(n) ────────────────────────
// Cenário: verificar frequentemente se um email já existe
// ❌ O(n) — percorre todos os utilizadores
boolean exists = userRepository.findAll()
.stream()
.anyMatch(u -> u.getEmail().equals(email));
// ✅ O(log n) — índice único na BD
// Na entidade:
@Column(unique = true)
private String email;
// Na query:
boolean exists = userRepository.existsByEmail(email);
// SELECT COUNT(*) FROM users WHERE email = ? — usa o índice único: O(log n)
// ✅ O(1) — cache em HashSet para verificações muito frequentes
Set<String> emailCache = new HashSet<>(userRepository.findAllEmails());
boolean exists = emailCache.contains(email); // O(1) — mas requer invalidação de cacheBig O aplica-se não só ao tempo mas também à memória. Uma solução que troca tempo por espaço pode ser óptima ou desastrosa dependendo do contexto — escalar memória é muito mais caro do que escalar CPU.
// Complexidade de espaço — exemplos práticos
// O(1) de espaço — memória constante, independente do input
int soma = 0;
for (int x : list) { soma += x; } // apenas uma variável extra, independente de n
// O(n) de espaço — memória proporcional ao input
List<Account> copia = new ArrayList<>(original); // duplica a lista em memória
// O(n) de espaço mas crítico em contexto web — paginação obrigatória
// ❌ Carregar todos os registos em memória para retornar ao cliente
List<Account> all = repository.findAll(); // 10M registos = potencialmente GBs de RAM
return all;
// ✅ Paginação — O(k) onde k é o tamanho da página (constante small)
Page<Account> page = repository.findByOwnerId(userId, PageRequest.of(0, 20));
return page.getContent(); // sempre 20 elementos em memória, independente do total
// O trade-off espaço-tempo com cache:
// Computação lenta mas O(1) de espaço:
double result = computeExpensive(input); // sempre recalcula
// Rápido mas O(n) de espaço (n = número de inputs distintos):
Map<Input, Double> cache = new HashMap<>();
double result = cache.computeIfAbsent(input, k -> computeExpensive(k));
// Troca memória por tempo — válido se os inputs são limitados e a computação é caraA complexidade algorítmica não é apenas uma preocupação de implementação interna — afecta directamente como uma API deve ser desenhada. Um endpoint que devolve todos os registos sem paginação é um endpoint com complexidade O(n) de tempo e espaço que vai degradar à medida que os dados crescem.
// Princípios de design de API guiados por complexidade:
// 1. Endpoints de colecção devem sempre ter paginação
// ❌ GET /api/accounts → retorna todos (O(n) tempo e espaço, não escalável)
// ✅ GET /api/accounts?page=0&size=20 → retorna 20 (O(k) espaço, O(log n) tempo com índice)
// 2. Filtros devem ser processados na BD, nunca em memória
// ❌ GET /api/accounts → filtra status=ACTIVE no código Java
// ✅ GET /api/accounts?status=ACTIVE → WHERE status = 'ACTIVE' com índice
// 3. Endpoints de lookup por ID devem usar índices
// GET /api/accounts/42
// → SELECT * FROM accounts WHERE id = 42 AND owner_id = 99
// → O(log n) com índice em id ou (id, owner_id)
// → O(n) sem índice — full table scan a cada pedido
// 4. Bulk operations para evitar O(n) de pedidos HTTP
// ❌ O(n) pedidos: for each id → POST /api/accounts/{id}/archive
// ✅ 1 pedido: POST /api/accounts/archive { "ids": [1, 2, 3, ...] }
// → UPDATE accounts SET status='ARCHIVED' WHERE id IN (...) AND owner_id = 99
// → O(k log n) onde k = número de IDs no batch
// 5. A query de isolamento lógico anti-IDOR é O(log n) com índice correcto
// SELECT * FROM accounts WHERE id = ? AND owner_id = ?
// Com índice em (id) ou (id, owner_id): O(log n) ✅
// Sem índice: O(n) — percorre toda a tabela para cada pedido autenticado ❌HashSet/HashMap O(1) em vez de List.contains() O(n).TreeMap O(log n) — chaves sempre ordenadas.findAllById() ou IN (...).WHERE id = ? AND owner_id = ? é O(log n) com índice em id — não há custo de segurança em performance.