📈 Intuição de crescimento (O(1), O(log n), O(n), O(n²))

Comparar algoritmos não é só comparar código. Também é preciso comparar o ritmo com que o custo cresce.

Como diferentes crescimentos se comparam quando n aumenta?

Mais importante do que decorar símbolos é perceber o que acontece quando n cresce de verdade.

A pergunta central

Se aumentarmos bastante o tamanho da entrada, qual tipo de algoritmo continua sob controle e qual começa a explodir?

Para responder, vamos olhar para algumas classes de crescimento muito comuns.

O(1): constante

Um algoritmo O(1) faz sempre a mesma quantidade de trabalho, independentemente do tamanho da entrada.

Exemplo:

def primeiro_elemento(lista):
    return lista[0]

Mesmo que a lista tenha 10 elementos ou 10 milhões, o acesso ao primeiro elemento continua sendo uma operação direta.

O(1) não significa "instantâneo". Significa apenas que o esforço não cresce com n.

O(log n): crescimento lento

Em algoritmos O(log n), o trabalho cresce muito devagar. Esse tipo de crescimento aparece quando, a cada passo, reduzimos bastante o problema.

Exemplo típico:

• busca binária

Se a cada etapa você elimina metade das possibilidades, o número de passos cresce lentamente mesmo quando n aumenta muito.

Para uma lista de 1 bilhão de elementos, a busca binária precisa de apenas cerca de 30 comparações no pior caso.

O(n): linear

Um algoritmo O(n) cresce em proporção direta ao tamanho da entrada.

Exemplo:

def imprimir_lista(lista):
    for item in lista:
        print(item)

Se a entrada dobra, o trabalho tende a dobrar também.

Esse é um crescimento comum e, em muitos casos, totalmente aceitável.

O(n log n): quase linear

Essa classe aparece bastante em algoritmos eficientes de ordenação e divisão do problema.

Ela cresce mais do que n, mas bem menos do que n².

Na prática, O(n log n) costuma continuar viável por muito mais tempo do que soluções quadráticas quando a entrada cresce.

O(n²): quadrático

Aqui o crescimento começa a pesar bastante.

Esse padrão aparece com frequência em loops aninhados sobre a mesma entrada.

Exemplo:

def comparar_todos(lista):
    for i in lista:
        for j in lista:
            print(i, j)

Se a entrada dobra, o trabalho não dobra: ele cresce muito mais.

Por isso, algoritmos quadráticos costumam funcionar bem com entradas pequenas, mas podem ficar caros rapidamente.

O(n³) e além

Quando temos três loops aninhados, por exemplo, o crescimento pode chegar a O(n³).

Acima disso, a escalabilidade piora ainda mais. Dependendo do contexto, esses algoritmos só são aceitáveis para entradas pequenas.

Crescimentos exponenciais

Em alguns problemas, o número de possibilidades cresce de forma explosiva, como em O(2^n).

Esse tipo de algoritmo se torna inviável muito cedo.

Um aumento pequeno em n já pode produzir um aumento enorme no trabalho.

É por isso que algoritmos exponenciais costumam ser tratados com muito cuidado.

Comparando intuitivamente

Uma forma simples de pensar é esta:

• O(1) quase não sente o crescimento de n
• O(log n) cresce muito devagar
• O(n) cresce de forma controlada
• O(n log n) ainda costuma ser bastante viável
• O(n²) já pesa bem mais
• O(n³) ou mais pode ficar caro rapidamente
• O(2^n) explode cedo

O que realmente importa ao comparar?

Nem sempre um algoritmo com classe "melhor" vence em qualquer entrada pequena. Constantes, implementação e contexto também influenciam.

Mas, quando a entrada cresce bastante, a classe de crescimento tende a se tornar o fator dominante.

É por isso que essa intuição é tão importante: ela ajuda a prever quais soluções escalam e quais só funcionam em cenários pequenos.

Resumo

• Classes de crescimento ajudam a comparar a escalabilidade de algoritmos.
• Crescimentos como O(1), O(log n) e O(n) tendem a escalar melhor.
• O(n log n) costuma ser muito eficiente na prática.
• O(n²) e acima exigem mais cuidado.
• Crescimentos exponenciais se tornam inviáveis rapidamente.

Com essa intuição, fica muito mais fácil olhar para um algoritmo novo e ter uma noção inicial de quão bem ele deve escalar.