Big-O com Exemplos de Código: Entenda a Complexidade Facilmente

1. Visão Geral

Big-O é a forma de descrever a taxa de crescimento do tempo de execução (ou memória) quando o tamanho da entrada aumenta. Este artigo não usa fórmulas matemáticas áridas, mas percorre cada nível de complexidade comum com código Java real, incluindo análise de qual linha gera o custo. Depois de ler, você conseguirá olhar para um trecho de código e adivinhar na hora se é O(1), O(n), O(n log n) ou O(n²) sem precisar contar manualmente.

2. O que é Big-O e Por Que Se Importar

Big-O responde à pergunta: “Se a entrada dobra, quanto o tempo de execução aumenta?” Ela descarta constantes e fatores menores, mantendo apenas a tendência de crescimento quando n (tamanho da entrada) tende ao infinito.

n = 1.000      -> O(n) executa ~1.000 passos
n = 1.000.000  -> O(n) executa ~1.000.000 passos (crescimento linear)
n = 1.000.000  -> O(n²) executa ~10^12 passos (crescimento muito rápido)

Dois trechos de código podem parecer iguais “à primeira vista”, mas ter complexidade completamente diferente se um deles tiver loops aninhados escondidos em uma chamada de função. Entender Big-O ajuda você a evitar escrever código que roda bem com 100 registros em teste, mas “congela” quando vai para produção com 10 milhões de registros.

Nota: Big-O descreve o pior caso (worst case) por convenção mais comum, a menos que explicitamente dito que é best-case ou average-case.

3. O(1) – Tempo Constante

O tempo de execução é sempre o mesmo, não importa o tamanho da entrada.

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get é O(1) em média
    }
}

get() em HashMap calcula o hash da chave e pula direto para o bucket correspondente, não depende da quantidade de elementos no mapa. Da mesma forma, acessar array[i] ou list.get(i) com ArrayList também é O(1) porque é só calcular o endereço de offset.

4. O(n) – Tempo Linear

O tempo de execução cresce proporcionalmente ao tamanho da entrada.

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // pode retornar cedo, mas no pior caso percorre tudo
            }
        }
        return false;
    }
}

O loop for percorre no máximo n elementos de orders. O pior caso acontece quando nenhum pedido está expirado, forçando a verificação de toda a lista. Este é o padrão O(n) clássico: um loop único, sem aninhamento.

4.1. Armadilha Comum: contains() dentro de um Loop

public class DuplicateChecker {

    // O(n²) porque contains() em List é O(n), chamado n vezes
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email) em ArrayList é O(n) porque precisa fazer uma busca linear. Chamá-lo dentro do loop for transforma toda a função em O(n²) — um erro muito fácil de cometer quando você não fica atento à estrutura de dados.

public class DuplicateChecker {

    // O(n) porque HashSet.add/contains é O(1)
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // add() retorna false se já existe
                return true;
            }
        }
        return false;
    }
}

Apenas mudando List para HashSet, a complexidade cai de O(n²) para O(n). Este é o exemplo mais prático mostrando que escolher a estrutura de dados certa é mais importante que “micro-otimizações”.

5. O(log n) – Tempo Logarítmico

Cada passo elimina metade do espaço de busca.

public class PriceLookup {

    // sortedPrices deve estar ordenado em ordem crescente antes
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Binary search reduz pela metade o array a cada volta do while, então com n = 1.000.000 são necessários cerca de 20 passos (log₂ 1.000.000 ≈ 20) para encontrar o resultado, em vez de percorrer linearmente um milhão de elementos.

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

Este teste confirma o comportamento correto tanto quando encontra (retorna o índice) quanto quando não encontra (retorna -1), os dois ramos mais importantes do binary search.

6. O(n log n) – Combinação de Linear e Logarítmico

Esta é a complexidade de algoritmos de ordenação eficientes como merge sort, quick sort (caso médio), ou Collections.sort().

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Collections.sort()/List.sort() em Java usa Timsort (variação do merge sort), garantindo O(n log n) no pior caso. Se você ver código chamando sort() dentro de um loop que executa n vezes, a complexidade total será multiplicada para O(n² log n) — um sinal de que precisa refatorar.

7. O(n²) – Tempo Quadrático

Dois loops aninhados, cada um percorrendo toda (ou quase toda) a entrada.

public class PairFinder {

    // Encontra todos os pares de produtos cuja soma de preço é igual ao alvo
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

O loop externo executa n vezes, o loop interno executa até n vezes para cada iteração do loop externo — o número total de comparações é aproximadamente n²/2, então a complexidade é O(n²). Com n = 10.000, são 50 milhões de comparações — ainda executa, mas fica notavelmente lento.

public class PairFinder {

    // O(n) porque HashSet guarda valores já vistos
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

Em vez de comparar cada par, precisamos apenas de um loop único e uma busca O(1) em HashSet. Esta é uma técnica muito comum de “trocar tempo por espaço”: usa mais memória para armazenar seen, mas reduz a complexidade de O(n²) para O(n).

8. O(2^n) – Tempo Exponencial

O tempo de execução dobra a cada vez que a entrada aumenta em 1 — comum em funções recursivas que calculam todos os subconjuntos.

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Ramo 1: não seleciona item[index]
        backtrack(items, index + 1, current, result);

        // Ramo 2: seleciona item[index]
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Cada elemento cria 2 ramos recursivos (seleciona ou não), então com n elementos temos 2^n subconjuntos. Com n = 20, já são mais de 1 milhão de subconjuntos; n = 40 nenhuma máquina vai terminar em tempo razoável. Este é um sinal de que você precisa considerar programação dinâmica (dynamic programming) se o problema permitir.

9. Comparação Rápida com Benchmark Real

Um exemplo de teste simples para “ver” a diferença entre O(n) e O(n²):

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n), então ainda é muito rápido com 100k elementos
    }
}

Se você tentar trocar hasDuplicateFast por hasDuplicateSlow com os mesmos 100.000 emails, o tempo de execução vai muito além de 500ms — prova visual da diferença entre O(n) e O(n²) com dados reais.

10. Tabela de Resumo e Regras de Identificação Rápida

Big-O	Indicador no código	Exemplo
O(1)	Sem loops, acesso direto (índice de array, HashMap.get)	map.get(key)
O(log n)	Cada passo elimina parte do espaço de busca	Binary search
O(n)	Um loop único percorrendo a entrada	for sobre List
O(n log n)	Loop combinado com sort ou divide-and-conquer	Collections.sort()
O(n²)	Loop dentro de loop, ambos percorrendo a entrada	Comparar cada par
O(2^n)	Recursão com 2 ramos em cada passo, sem poda	Gerar todos os subconjuntos

Regra de contagem rápida: conte os loops aninhados que percorrem a entrada — cada nível de loop adiciona um “grau de n”. Se dentro do loop há chamadas de função de biblioteca (contains, sort, indexOf), verifique a complexidade daquela função antes de somar ao total.

Nota: Big-O não diz nada sobre as constantes reais. Um algoritmo O(n) com uma grande constante (por exemplo, ler um arquivo a cada iteração) pode ser mais lento que O(n log n) com uma constante pequena quando n não é grande o suficiente. Não otimize Big-O cegamente sem medir (profile) o comportamento real.

11. Conclusão

Big-O é uma ferramenta para prever tendências, não um número absoluto — mas essa tendência decide se seu código sobrevive ou falha quando os dados crescem. A dica mais prática: toda vez que escrever um loop, pergunte-se “será que há alguma chamada de função O(n) dentro deste loop?” — essa é a origem da maioria dos erros O(n²) indesejados na prática. Dominar os 6 níveis de complexidade acima é suficiente para ler, entender e questionar a maioria do código de algoritmos que você encontra diariamente.