A Régua da Eficiência: Dominando o Big O

O(1) - Tempo Constante 🏆

O que é: O tempo de execução não depende do tamanho da entrada (n). É o Santo Graal da eficiência.

Exemplo: Acessar um elemento em um array pelo índice.

function getFirstElement(arr) {
  return arr[0]; // Sempre 1 operação, não importa o tamanho do array
}

O(log n) - Tempo Logarítmico 🚀

O que é: O tempo de execução cresce de forma logarítmica. Geralmente, ocorre em algoritmos que "quebram" o problema pela metade a cada passo. É extremamente eficiente.

Exemplo: Busca Binária (Binary Search) em um array ordenado.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    let 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; // A cada passo, o espaço de busca é dividido por 2
}

O(n) - Tempo Linear 🏃

O que é: O tempo de execução cresce na mesma proporção que o tamanho da entrada. Se a entrada dobra, o tempo dobra. É a complexidade mais comum para uma primeira abordagem ("força bruta").

Exemplo: Encontrar um item em uma lista não ordenada.

function findValue(arr, value) {
  for (let i = 0; i < arr.length; i++) { // O loop passa por cada item
    if (arr[i] === value) return i;
  }
  return -1;
}

O(n log n) - Tempo Log-Linear 💨

O que é: Um pouco mais lento que O(n), mas ainda muito eficiente. É a complexidade dos melhores algoritmos de ordenação baseados em comparação.

Exemplo: Merge Sort, Quick Sort (no caso médio).

O(n²) - Tempo Quadrático 🐌

O que é: O tempo de execução cresce ao quadrado do tamanho da entrada. Geralmente envolve um loop aninhado dentro de outro, percorrendo a mesma coleção. Fica lento rapidamente.

Exemplo: Encontrar pares duplicados em uma lista usando dois loops.

function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) { // Loop dentro de loop
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

O(2ⁿ) - Tempo Exponencial 🐢

O que é: O tempo de execução dobra a cada novo elemento adicionado à entrada. Fica inviável para entradas mesmo que moderadamente grandes. Frequentemente visto em soluções recursivas que não usam memoização.

Exemplo: Cálculo de Fibonacci recursivo (a versão ingênua).

Regra 1: Foco no Pior Caso (Worst-Case)

O Big O descreve a performance no pior cenário possível. Se um algoritmo pode ser muito rápido na maioria das vezes (melhor caso ou caso médio), mas lento em uma situação específica, é essa situação lenta que define sua complexidade. Isso nos dá uma garantia de performance.

function findItem(array, item) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === item) {
      return "Encontrado!"; // Sai mais cedo
    }
  }
  return "Não encontrado.";
}
// Melhor caso: O item é o primeiro. Complexidade O(1).
// Pior caso: O item é o último ou não existe. Complexidade O(n).
// Nossa classificação Big O é sempre o pior caso: O(n).

Regra 2: Ignore as Constantes

O(2n) vira O(n). O que importa é a taxa de crescimento, não o valor exato. 2n cresce na mesma taxa que n (linearmente).

function printItems(arr) {
  for (const item of arr) {
    console.log(item); // O(n)
  }
  for (const item of arr) {
    console.log(item); // O(n)
  }
}
// Total: O(n + n) = O(2n) -> Simplifica para O(n)

Regra 3: Ignore os Termos Não-Dominantes

O(n² + n) vira O(n²). Quando 'n' fica muito grande, a parte 'n²' domina completamente o crescimento, tornando o '+ n' irrelevante para a análise da escala.

function printItemsAndPairs(arr) {
  for (const item of arr) { // O(n)
    console.log(item);
  }
  for (let i = 0; i < arr.length; i++) { // O(n²)
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}
// Total: O(n + n²) -> Simplifica para O(n²)

Regra 4: Some Complexidades para Passos Sequenciais (Inputs Diferentes)

Se você tem um loop O(n) seguido por um loop O(m) para inputs diferentes, a complexidade total é O(n + m). Não podemos simplificar porque não sabemos a relação entre n e m.

function processTwoArrays(arr1, arr2) {
  for (const item of arr1) { // O(n)
    console.log(item);
  }
  for (const item of arr2) { // O(m)
    console.log(item);
  }
}
// Total: O(n + m)

Regra 5: Multiplique Complexidades para Passos Aninhados

Se você tem um loop O(n) com outro loop O(n) dentro dele, a complexidade é O(n * n) = O(n²). Se o loop interno fosse sobre um input 'm', seria O(n * m).

function createPairs(arr) {
  for (let i = 0; i < arr.length; i++) { // Loop externo: n vezes
    for (let j = 0; j < arr.length; j++) { // Loop interno: n vezes
      console.log(arr[i], arr[j]); // Executa n*n vezes
    }
  }
}
// Total: O(n * n) = O(n²)