Notação Big-O

A notação Big-O descreve como o custo de um algoritmo (em tempo ou memória) cresce à medida que aumenta o tamanho da entrada n. Ela ignora constantes e termos menores para focar no comportamento em larga escala.

Complexidades comuns (da melhor à pior)

Notação	Nome	Exemplo
`O(1)`	Constante	Acessar `arr[0]`
`O(log n)`	Logarítmica	Busca binária
`O(n)`	Linear	Percorrer um array
`O(n log n)`	Linearítmica	Merge sort, quick sort
`O(n²)`	Quadrática	Bubble sort, laços aninhados
`O(2ⁿ)`	Exponencial	Fibonacci recursivo ingênuo

Exemplos

// O(1): não depende do tamanho
function primeiro(arr) {
  return arr[0];
}

// O(n): uma passada pelo array
function soma(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n²): um laço dentro de outro
function pares(arr) {
  const saida = [];
  for (const a of arr) {
    for (const b of arr) {
      saida.push([a, b]);
    }
  }
  return saida;
}

A regra prática: conte os laços aninhados sobre a entrada. Dois laços aninhados sobre n costumam ser O(n²).

Exemplos

Comparar o número de operações

function operacoesLinear(n) {
  let ops = 0;
  for (let i = 0; i < n; i++) ops++;
  return ops;
}
function operacoesQuadratico(n) {
  let ops = 0;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) ops++;
  return ops;
}
console.log("Linear n=10:", operacoesLinear(10));
console.log("Quadrático n=10:", operacoesQuadratico(10));