Big O na Prática

O que é

Big O descreve como o tempo de execução ou o uso de memória de um algoritmo cresce conforme o tamanho da entrada n aumenta. Ele foca no comportamento assintótico, ou seja, na tendência de crescimento quando n fica muito grande, ignorando detalhes pequenos como constantes, e normalmente considerando o pior caso.

Exemplo: um algoritmo com custo 3n² + 5n + 10 é classificado como O(n²).

Por que importa

• Prever escalabilidade antes de ir para produção.
• Comparar soluções sem precisar de benchmarks.
• Base para decisões de arquitetura e design.

Notações relacionadas

• O (Big O) - limite superior (pior caso).
• Ω (Big Omega) - limite inferior (melhor caso).
• Θ (Big Theta) - limite justo (quando melhor e pior coincidem).

Na prática, "Big O" é usado como sinônimo genérico de "complexidade", mesmo quando tecnicamente seria Θ.

Complexidade Temporal

Ordem de crescimento, do mais rápido ao mais lento:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

O(1) - Constante

O tempo não depende do tamanho da entrada.

function getFirst(arr) {
  return arr[0];
}

Exemplos reais: acesso a array por índice, push/pop em stack, get/put em HashMap (amortizado), leitura de variável.

O(log n) - Logarítmica

A cada iteração, o problema é reduzido por uma fração fixa (geralmente pela metade).

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Exemplos reais: busca binária, operações em árvores balanceadas (AVL, Red-Black), busca em B-Tree (índices de banco de dados).

O(n) - Linear

Percorre todos os elementos uma vez.

function sum(arr) {
  let total = 0;
  for (const value of arr) total += value;
  return total;
}

Exemplos reais: busca linear, cópia de array, varredura de linked list, validação de todos os itens de um formulário.

O(n log n) - Linearítmica

Divide o problema em log n níveis e processa n elementos em cada nível. É o limite inferior teórico para algoritmos de ordenação baseados em comparação.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

Exemplos reais: Merge Sort, Quick Sort (médio), Heap Sort, Timsort - que é o algoritmo padrão de Arrays.sort() em Java, list.sort() em Python e Array.prototype.sort() nos engines JS modernos.

O(n²) - Quadrática

Dois loops aninhados sobre a entrada.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

Exemplos reais: Bubble Sort, Insertion Sort, Selection Sort, comparar todos os pares de uma coleção, detecção naive de duplicados.

O(n³) - Cúbica

Três loops aninhados.

function multiplyMatrices(a, b, n) {
  const result = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        result[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return result;
}

Exemplos reais: multiplicação ingênua de matrizes, Floyd-Warshall (todos os caminhos mínimos de grafo).

O(2ⁿ) - Exponencial

Cada elemento gera duas ramificações. Inviável a partir de n ≈ 30.

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

Exemplos reais: Fibonacci recursivo sem memoização, Subset Sum força bruta, geração de todos os subconjuntos de um conjunto.

O(n!) - Fatorial

Explora todas as permutações possíveis. Inviável já em n ≈ 12.

function permutations(arr) {
  if (arr.length <= 1) return [arr];
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const p of permutations(rest)) {
      result.push([arr[i], ...p]);
    }
  }
  return result;
}

Exemplos reais: Traveling Salesman força bruta, gerar todas as permutações/anagramas.

Complexidade Espacial

Mede o espaço adicional consumido pelo algoritmo em função de n. Não conta a entrada em si, apenas memória auxiliar alocada (variáveis, estruturas criadas, pilha de chamadas).

O(1) - Constante

Usa memória fixa, independente de n.

function max(arr) {
  let result = -Infinity;
  for (const value of arr) {
    if (value > result) result = value;
  }
  return result;
}

Exemplos reais: Bubble Sort (in-place), swap de variáveis, contadores, two-pointer sem alocação extra.

O(log n) - Logarítmica

Comum em recursão que divide o problema pela metade - a pilha de chamadas cresce proporcionalmente a log n.

function binarySearchRecursive(arr, target, left, right) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
  return binarySearchRecursive(arr, target, left, mid - 1);
}

Exemplos reais: busca binária recursiva, Quick Sort (espaço da pilha no caso médio).

O(n) - Linear

Aloca estrutura proporcional à entrada.

function double(arr) {
  return arr.map(x => x * 2);
}

Exemplos reais: criar cópia de array, recursão com profundidade n (fatorial recursivo), HashMap com n chaves, memoização simples de Fibonacci.

O(n log n) - Linearítmica

Merge Sort não in-place aloca arrays temporários a cada nível da divisão.

Exemplos reais: Merge Sort com buffer auxiliar, alguns algoritmos de divisão e conquista.

O(n²) - Quadrática

Matriz n × n. Comum em programação dinâmica sobre pares.

function createAdjacencyMatrix(n) {
  return Array.from({ length: n }, () => new Array(n).fill(0));
}

Exemplos reais: matriz de adjacência de grafo, tabela DP de Longest Common Subsequence, Edit Distance.

Tabela de crescimento

Aproximação de operações para cada classe, conforme n cresce:

Como analisar na prática

1. Loops sequenciais somam: O(n) + O(n) = O(n).
2. Loops aninhados multiplicam: dois loops de tamanho n → O(n²).
3. Constantes e termos menores são descartados: O(3n² + 100n + 5) = O(n²).
4. Pior caso é o padrão, mas considere também o caso amortizado - ex: ArrayList.add em Java é O(1) amortizado mesmo com redimensionamentos O(n) ocasionais.
5. Variáveis diferentes ficam separadas: loops sobre coleções a e b → O(a + b), não O(n). Importa quando os tamanhos diferem ordens de grandeza.
6. Recursão: tempo = chamadas × trabalho por chamada; espaço = profundidade máxima da pilha.

Armadilhas comuns

• Array.includes(), indexOf(), in em array → O(n), não O(1). Para lookup rápido use Set ou Map.
• Concatenação de strings dentro de loop em muitas linguagens → O(n²) por imutabilidade. Use StringBuilder (Java) ou array.join() (JS).
• slice()/concat() → O(n) cada chamada. Dentro de um loop viram O(n²) escondido.
• Recursão sem memoização (ex: Fibonacci) → explode para O(2ⁿ). Com memoização cai para O(n) tempo e O(n) espaço.
• Complexidade de I/O e rede quase sempre domina a de CPU - otimizar de O(n²) para O(n log n) é irrelevante se o código faz 1000 chamadas HTTP sequenciais.
• Stream pipelines em Java e .map().filter().reduce() encadeados em JS escondem múltiplas passadas pela coleção - cada operação é O(n), então a cadeia vira O(kn) com k = número de operações.

Referência rápida por estrutura de dados

• Assumindo acesso direto ao nó (inserção/remoção em posição conhecida). † Caso médio/amortizado. Pior caso pode ser O(n) para hash com muitas colisões e BST desbalanceada.