O que é Big O? e o Vilão O(N^2)

Source: Dev.to

Complexidade de Algoritmos com Elixir: Entendendo o O(N²) e Por que sua lista é tão lenta?

Se você programa em Elixir ou qualquer outra linguagem e já viu seu código funcionar perfeitamente com 10 itens, mas travar com 10 000, você esbarrou na Complexidade de Algoritmos.

A notação Big O O(...) não mede o tempo em segundos, mas sim a regra de crescimento do tempo de execução em relação ao tamanho da entrada (N). É a ferramenta mais importante para escrever código que escala.

🟢 O(1): Complexidade Constante

O tempo de execução é sempre o mesmo, não importa se sua lista tem 10 elementos ou 1 milhão.

Exemplo em Elixir – prepend (inserir no início):

# O(1): Cria um novo nó que aponta para a lista antiga.
new_list = [novo_item | lista_antiga]

# O(1): Acesso à cabeça
[head | _] = new_list

Essa é a operação mais comum em código funcional e a razão pela qual a criação de listas em Elixir é tão rápida.

🟡 O(N): Complexidade Linear

O tempo de execução cresce proporcionalmente ao tamanho da entrada. Se a lista dobra de tamanho, o tempo dobra.

Exemplo em Elixir – varrer a lista (map, reduce) ou anexar no final:

# O(N): Percorre cada elemento da lista
sum = Enum.reduce(list, 0, &(&1 + &2))

# O(N): Para anexar no final, o sistema deve percorrer a lista inteira.
list = list ++ [item_no_fim]

🔥 O(N²): O Vilão Quadrático

A complexidade O(N²) é o seu pior inimigo para escalabilidade. Se a entrada (N) dobra de tamanho, o tempo de execução quadruplica (2² = 4).

Causa: laços de repetição aninhados onde o loop interno depende do tamanho total da entrada.

Exemplo prático – Checagem ingênua de duplicatas

def check_duplicate_slow(list) do
  # Enum.any? itera pela lista: N vezes
  Enum.any?(list, fn current_element ->
    # Para cada elemento, varre a lista inteira novamente: N vezes
    list
    |> Enum.filter(&(&1 == current_element))
    |> Enum.count() > 1
  end)
end

Análise

• Enum.any? externo executa N vezes.
• Para cada execução, Enum.filter interno varre toda a lista (N elementos).
• Total de operações ≈ N × N = O(N²).

Se N = 10 000, o algoritmo fará 100 000 000 operações (cem milhões) – um crescimento insustentável!

Próxima parada: o salto para O(N)

A solução O(N²) é fácil de escrever, mas destrói a performance. Existe uma forma de resolver o problema de duplicatas visitando cada elemento apenas uma vez, transformando o algoritmo em um rápido O(N) usando estruturas de dados com acesso O(1). No próximo post, exploraremos essa técnica.

Migração de O(N²) para O(N)!