Notação Big O: Trabalhando com Complexidade de Algoritmos

“Medir é saber.”, Lord Kelvin
Se você não consegue expressar a eficiência do seu algoritmo, você não o entende de verdade.

Neste artigo, resolvi trazer um conteúdo um pouco diferente para vocês, mais focado em fundamentos de performance de algoritmos. Muitos anos atrás em uma entrevista, fazendo os testes para a vaga, em 2 cenários que eu havia atingido o objetivo do teste com os resultados corretos, o responsável técnico me questionou durante a entrevista se eu conseguia ver oportunidades de melhoria na lógica e se eu já havia ouvido falar de notação Big O. Eu já tinha ouvido falar, mas não de forma aprofundada, que pudesse realmente explicar algo para ele.

Esse artigo fica como uma revisão para quem já é mais experiente e também um ponto inicial de estudos para você que ainda está começando. Vamos lá então…

1. O que é a Notação Big O?

A notação Big O é uma linguagem matemática que descreve como o tempo de execução ou o consumo de memória de um algoritmo cresce à medida que o tamanho da entrada aumenta. Ela não mede segundos ou bytes: ela mede a taxa de crescimento.

Quando dizemos que um algoritmo é O(n), estamos dizendo: “no pior caso, o tempo de execução cresce de forma proporcional ao tamanho da entrada”. Se a entrada dobra, o tempo aproximadamente dobra.

A notação Big O responde a uma pergunta fundamental:

“Se eu multiplicar o tamanho da entrada por 10, o que acontece com o tempo de execução?“

2. Origens Históricas

A notação que usamos hoje tem raízes profundas na matemática do século XIX:

Paul Bachmann (1894): O matemático alemão introduziu o símbolo O pela primeira vez no segundo volume do seu livro Analytische Zahlentheorie (Teoria Analítica dos Números). A letra O vem da palavra alemã Ordnung, que significa “ordem de aproximação”.

Edmund Landau (1909): Outro teórico dos números alemão adotou a notação de Bachmann e a expandiu, criando também a notação o (little-o). Por isso, ambos os símbolos são frequentemente chamados de símbolos de Landau ou notação de Bachmann-Landau.

G. H. Hardy e J. E. Littlewood (1914): Introduziram o símbolo Ω (Omega) e contribuíram para formalizar a família de notações assintóticas.

Donald Knuth (anos 1970): Considerado o pai da análise de algoritmos, Knuth foi quem popularizou a notação Big O na ciência da computação. Ele também introduziu a notação Θ (Theta) e propôs uma definição mais precisa para Ω, estabelecendo o padrão que usamos até hoje para classificar algoritmos.

3. A Família de Notações Assintóticas

“Assintótico” é um termo matemático para descrever como uma função se comporta quando o valor de entrada cresce muito. Pense assim: não importa o que acontece com n=10 ou n=100, importa o que acontece quando n vira um milhão. Antes de mergulhar no Big O, é importante entender que ele faz parte de uma família:

Na prática do dia a dia como desenvolvedor, Big O é a notação que mais importa, pois queremos saber: “qual o pior que pode acontecer?”

4. As Classes de Complexidade

Aqui está o coração da questão: as classes de complexidade, da mais eficiente à mais custosa.

4.1. O(1): Tempo Constante

O que significa: O tempo de execução não muda, independente do tamanho da entrada.

Analogia: Abrir uma gaveta específica de um armário. Não importa se o armário tem 5 ou 500 gavetas: você vai direto na que precisa.

// Acessar elemento por índice
int[] numeros = { 10, 20, 30, 40, 50 };
int valor = numeros[2]; // Sempre 1 operação, O(1)

// Acessar valor em Dictionary por chave
var config = new Dictionary<string, string> { ["db_host"] = "localhost" };
string host = config["db_host"]; // O(1)

Exemplos no mundo real: acesso a um HashMap/Dictionary por chave, operações push/pop em uma stack, verificar se um número é par ou ímpar.

4.2. O(log n): Tempo Logarítmico

O que significa: A cada passo, o problema é dividido pela metade. Extremamente eficiente mesmo para entradas enormes.

Analogia: Procurar uma palavra no dicionário. Você não lê página por página: abre no meio, decide se a palavra está antes ou depois, e repete o processo. Com 1.000.000 de palavras, você precisa de no máximo ~20 passos.

// Busca binária
int BuscaBinaria(int[] arr, int alvo)
{
    int esquerda = 0, direita = arr.Length - 1;

    while (esquerda <= direita)
    {
        int meio = (esquerda + direita) / 2;

        if (arr[meio] == alvo) return meio;
        if (arr[meio] < alvo) esquerda = meio + 1;
        else direita = meio - 1;
    }

    return -1; // não encontrado
}

Por que log n? Porque log₂(n) é o número de vezes que você pode dividir n por 2 até chegar a 1.

4.3. O(n): Tempo Linear

O que significa: O tempo cresce proporcionalmente ao tamanho da entrada. Se a entrada dobra, o tempo dobra.

Analogia: Ler um livro página por página. 200 páginas = 200 minutos, 400 páginas = 400 minutos.

// Busca linear
int BuscaLinear(int[] arr, int alvo)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == alvo) return i;
    }
    return -1;
}

// Somar todos os elementos
int SomarTodos(int[] arr)
{
    int soma = 0;
    foreach (var num in arr) // Executa n vezes
        soma += num;
    return soma;
}

4.4. O(n log n): Tempo Linearítmico

O que significa: É o “sweet spot” dos algoritmos de ordenação eficientes. O nome vem da combinação de linear com logarítmico: o algoritmo faz n operações, mas em cada uma divide o problema logaritmicamente.

Analogia: Organizar um baralho usando Merge Sort: você divide as cartas em grupos menores, ordena cada grupo e junta tudo de volta.

// Merge Sort
void MergeSort(int[] arr, int esquerda, int direita)
{
    if (esquerda < direita)
    {
        int meio = (esquerda + direita) / 2;
        MergeSort(arr, esquerda, meio);       // Divide: log n
        MergeSort(arr, meio + 1, direita);    // Divide: log n
        Merge(arr, esquerda, meio, direita);  // Combina: n
    }
}

Algoritmos famosos nesta categoria: Merge Sort, Quick Sort (caso médio), Heap Sort, Tim Sort (usado pelo .NET e JavaScript internamente).

4.5. O(n²): Tempo Quadrático

O que significa: Para cada elemento, você percorre todos os outros elementos. Loops aninhados são o sinal clássico.

Analogia: Em uma festa com 100 pessoas, cada pessoa cumprimenta todas as outras. São quase 10.000 apertos de mão.

// Bubble Sort (exemplo clássico de O(n²))
void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)              // n vezes
    {
        for (int j = 0; j < n - i - 1; j++) // n vezes
        {
            if (arr[j] > arr[j + 1])
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
        }
    }
}

// Encontrar duplicatas com força bruta: O(n²)
bool TemDuplicata(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
        for (int j = i + 1; j < arr.Length; j++)
            if (arr[i] == arr[j]) return true;
    return false;
}

// Versão O(n) usando HashSet:
bool TemDuplicataOtimizado(int[] arr)
{
    var vistos = new HashSet<int>();
    foreach (var num in arr)
    {
        if (!vistos.Add(num)) return true; // Add retorna false se já existe
    }
    return false;
}

4.6. O(2ⁿ): Tempo Exponencial

O que significa: O tempo dobra a cada elemento adicionado na entrada. Cresce de forma explosiva.

Analogia: Imagine que a cada nova pergunta em uma prova, o número de combinações de respostas possíveis dobra.

// Fibonacci recursivo ingênuo (O(2^n))
int Fibonacci(int n)
{
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
    // Cada chamada gera 2 novas chamadas
}

// Memoization: guardar o resultado de cada chamada para não recalcular.
// O custo cai de O(2^n) para O(n).
int FibonacciOtimizado(int n, Dictionary<int, int> cache = null)
{
    cache ??= new Dictionary<int, int>();
    if (n <= 1) return n;
    if (cache.ContainsKey(n)) return cache[n];

    cache[n] = FibonacciOtimizado(n - 1, cache)
             + FibonacciOtimizado(n - 2, cache);
    return cache[n];
}

4.7. O(n!): Tempo Fatorial

O que significa: O algoritmo testa todas as permutações possíveis. Só é viável para entradas muito pequenas (n < 12 a 15).

Analogia: Organizar 10 pessoas em uma fila testando todas as ordens possíveis = 3.628.800 combinações.

// Problema do Caixeiro Viajante (Brute Force)
// Testa todas as n! rotas possíveis
int CaixeiroViajante(int[,] distancias, int n)
{
    var cidades = Enumerable.Range(1, n - 1).ToArray();
    int menorDistancia = int.MaxValue;

    foreach (var permutacao in Permutacoes(cidades))
    {
        int distanciaAtual = CalcularRota(distancias, permutacao);
        menorDistancia = Math.Min(menorDistancia, distanciaAtual);
    }

    return menorDistancia;
}

5. Tabela Comparativa Completa

6. Regras Práticas para Calcular Big O

Calcular Big O na prática segue um conjunto de regras simples:

Regra 1: Ignore constantes

O(2n) → O(n), O(500) → O(1), O(n/2) → O(n)

Constantes não importam porque Big O descreve comportamento para entradas muito grandes. Quando n = 1 bilhão, a diferença entre n e 2n é irrelevante comparada à diferença entre n e n².

Regra 2: Ignore termos menores

O(n² + n) → O(n²), O(n + log n) → O(n)

O termo dominante é o que define a taxa de crescimento. Quando n é grande, n² torna n insignificante.

Regra 3: Loops sequenciais somam

// Primeiro loop: O(n)
for (int i = 0; i < n; i++) { /* ... */ }

// Segundo loop: O(m)
for (int j = 0; j < m; j++) { /* ... */ }

// Total: O(n + m)
// Se n == m: O(2n) → O(n)

Regra 4: Loops aninhados multiplicam

// Loop externo: O(n)
for (int i = 0; i < n; i++)
{
    // Loop interno: O(n)
    for (int j = 0; j < n; j++)
    {
        // Operação: O(1)
    }
}
// Total: O(n) × O(n) = O(n²)

Regra 5: Dividir pela metade a cada passo = log n

// A cada iteração, i dobra → log₂(n) iterações
for (int i = 1; i < n; i *= 2)
{
    // O(1)
}
// Total: O(log n)

7. Complexidade de Espaço (Space Complexity)

Big O não serve apenas para tempo: também medimos memória.

// O(1) espaço — usa variáveis fixas
int Soma(int[] arr)
{
    int total = 0; // 1 variável, independente de n
    for (int i = 0; i < arr.Length; i++)
        total += arr[i];
    return total;
}

// O(n) espaço — cria nova estrutura proporcional à entrada
int[] Duplicar(int[] arr)
{
    int[] resultado = new int[arr.Length]; // array de tamanho n
    for (int i = 0; i < arr.Length; i++)
        resultado[i] = arr[i] * 2;
    return resultado;
}

// O(n) espaço — recursão cria n frames na call stack
int Fatorial(int n)
{
    if (n <= 1) return 1;
    return n * Fatorial(n - 1); // n chamadas empilhadas
}

8. Complexidade de Operações Comuns em Estruturas de Dados

9. Como Medir na Prática

9.1. Análise estática (leitura do código)

A forma mais confiável: olhe o código e aplique as regras da seção 6.

// Exercício: qual a complexidade?
int EncontrarMaximo(int[] arr)
{
    int max = arr[0];                       // O(1)
    for (int i = 1; i < arr.Length; i++)    // O(n)
    {
        if (arr[i] > max) max = arr[i];     // O(1)
    }
    return max;                             // O(1)
}
// Resposta: O(1) + O(n) × O(1) + O(1) = O(n)

9.2. Benchmark empírico

Meça o tempo para diferentes tamanhos de entrada e observe o padrão:

// Benchmark simples
using System.Diagnostics;

void Benchmark(Action<int[]> algoritmo, string nome)
{
    int[] tamanhos = { 1_000, 5_000, 10_000, 50_000, 100_000 };

    foreach (var n in tamanhos)
    {
        var arr = Enumerable.Range(0, n)
                            .OrderBy(_ => Random.Shared.Next())
                            .ToArray();

        var sw = Stopwatch.StartNew();
        algoritmo(arr);
        sw.Stop();

        Console.WriteLine($"{nome} | n={n,7:N0} | {sw.ElapsedMilliseconds,6}ms");
    }
}

Se o tempo cresce proporcionalmente ao tamanho → O(n). Se o tempo quadruplica quando n dobra → O(n²). Se o tempo mal muda quando n dobra → O(log n) ou O(1).

9.3. BenchmarkDotNet (profissional em .NET)

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

[MemoryDiagnoser]
public class SortBenchmarks
{
    [Params(100, 1_000, 10_000, 100_000)]
    public int N;

    private int[] _data = null!;

    [GlobalSetup]
    public void Setup()
    {
        _data = Enumerable.Range(0, N)
                          .OrderBy(_ => Random.Shared.Next())
                          .ToArray();
    }

    [Benchmark]
    public void ArraySort() => Array.Sort((int[])_data.Clone());

    [Benchmark]
    public void BubbleSort()
    {
        var arr = (int[])_data.Clone();
        for (int i = 0; i < arr.Length; i++)
            for (int j = 0; j < arr.Length - i - 1; j++)
                if (arr[j] > arr[j + 1])
                    (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
    }
}

// Executar: BenchmarkRunner.Run<SortBenchmarks>();

10. Armadilhas e Erros Comuns

❌ “Meu algoritmo O(n²) é rápido com 100 elementos”

Sim, para n pequeno tudo funciona. Big O importa quando n cresce. Um O(n²) com n=100 faz 10.000 operações. Com n=1.000.000, faz 10¹², uma diferença de 100 milhões de vezes.

❌ “O(1) é sempre melhor que O(n)”

Nem sempre na prática. Um O(1) que faz 1.000.000 de operações constantes é pior que um O(n) para n < 1.000.000. Big O descreve tendência, não valor absoluto.

❌ Confundir caso médio com pior caso

O Quick Sort é O(n log n) no caso médio, mas O(n²) no pior caso (array já ordenado com pivot ruim). Para aplicações críticas, considere o pior caso.

❌ Ignorar complexidade de espaço

Um algoritmo O(n) em tempo que usa O(n²) de memória pode ser pior que um O(n²) em tempo com O(1) de memória, dependendo das restrições do sistema.

❌ Esquecer o custo real de métodos nativos

É comum tratar qualquer chamada de método como “rápida”, mas muitos métodos da biblioteca padrão têm custo linear ou pior. No exemplo abaixo, o código parece O(n), mas List<T>.Contains() percorre a lista inteira a cada chamada, tornando o resultado O(n²):

// Parece O(n), mas é O(n²)!
List<string> RemoverDuplicatas(string[] arr)
{
    var resultado = new List<string>();
    foreach (var item in arr)                 // O(n)
    {
        if (!resultado.Contains(item))         // O(n) — Contains faz busca linear!
            resultado.Add(item);
    }
    return resultado;
}

// Correção: O(n) usando HashSet
IEnumerable<string> RemoverDuplicatasOtimizado(string[] arr)
{
    return new HashSet<string>(arr); // O(1) por inserção
}

O hábito de consultar a documentação para confirmar a complexidade de métodos nativos faz diferença quando o volume de dados cresce.

11. Big O no Dia a Dia do Desenvolvedor

Quando Big O importa de verdade:

1. Entrevistas técnicas: É uma das perguntas mais frequentes em entrevistas de empresas de tecnologia.

2. APIs com alto tráfego: Uma API que processa 10.000 requests/segundo com um endpoint O(n²) vai travar seu servidor.

3. Processamento de dados em lote: ETLs, migrations, relatórios sobre milhões de registros.

4. Escolha de estrutura de dados: Saber que Dictionary<K,V> tem busca O(1) vs List<T>.Contains() com O(n) pode fazer a diferença entre um sistema responsivo e um sistema lento.

5. Code review: Identificar loops aninhados desnecessários ou operações O(n) dentro de loops.

Padrões de otimização comuns:

12. Resumo Visual Final

Referências

• Bachmann, P. (1894). Die Analytische Zahlentheorie. Leipzig: B. G. Teubner.
• Landau, E. (1909). Handbuch der Lehre von der Verteilung der Primzahlen. Leipzig: B. G. Teubner.
• Knuth, D. (1976). “Big Omicron and big Omega and big Theta.” ACM SIGACT News, 8(2), 18–24.
• Cormen, T. H. et al. Introduction to Algorithms (CLRS), MIT Press.

Concluindo

Lembre-se: Big O é uma ferramenta de comunicação. Quando você diz “esse algoritmo é O(n log n)”, todo desenvolvedor no mundo entende exatamente o que você quer dizer sobre seu comportamento em escala. Dominar essa linguagem é essencial para escrever software que funciona não apenas hoje, mas quando seus dados crescerem 100x.

Espero que este artigo tenha sido útil para vocês, pois ele representa muito algo que gostaria de ter lido antes daquela entrevista que mencionei na introdução do artigo.

Um abraço e até a próxima!