"A diferença entre um bom programador e um excelente programador não é quanto código ele escreve — é quanto código ele evita escrevendo escolhendo o algoritmo certo."
Big O descreve como tempo ou espaço crescem quando o input aumenta — não velocidade absoluta em segundos, mas taxa de crescimento.
// O(n²) — loops aninhadosfor (let i = 0; i < n; i++) for (let j = 0; j < n; j++) { /* ... */ } // O(log n) — busca bináriawhile (left <= right) { mid = ...; /* elimina metade */ }Neste guia da série 33 Conceitos JS — projeto open source criado por Leonardo Maldonado — você aprende a analisar código, escolher algoritmos e aplicar padrões de entrevista.
Pré-requisitos: Data Structures, Recursion e Map, Reduce & Filter.
// metadados do artigo
{
"tag": "advanced topics",
"readTime": "22 min",
"author": "Vanderlei José Alamino",
"source": "33jsconcepts.com",
"series": "33 Conceitos JS",
"part": {
"current": 36,
"total": 38
}
}Fonte de referência
Conteúdo adaptado a partir do guia original em inglês.
seção
O(1) → endereço exato — mesmo tempo com 10 ou 10.000 casasO(n) → checa cada casa — dobra input, dobra tempoO(n²) → compara cada par — 100 casas = 10.000 comparaçõesBig O mede escalabilidade e pior caso — ignora constantes (O(2n) → O(n)).
seção
Mede: taxa de crescimento, pior caso, comparação entre algoritmos.
Não mede: ms reais, hardware, memória exata (isso é space complexity).
Regra de ouro: O(n) com 1ms/elem pode perder para O(n²) em n pequeno — mas n grande, O(n) sempre vence.
seção
| Big O | Nome | Exemplo | 1M itens (ordem) |
|---|---|---|---|
| O(1) | Constante | arr[i], Map.get | 1 op |
| O(log n) | Logarítmica | Busca binária | ~20 ops |
| O(n) | Linear | loop simples | ~1M ops |
| O(n log n) | Linearítmica | sort() | ~20M ops |
| O(n²) | Quadrática | loops aninhados | ~1T ops |
arr[2]; // O(1)map.get('key'); // O(1)arr.push(6); // O(1)arr.indexOf(5); // O(n)[...arr].sort(); // O(n log n)log₂(1.000.000) ≈ 20 — busca binária escala muito bem.
seção
arr.length)function example(arr) { console.log(arr[0]); // O(1) for (const x of arr) { } // O(n) for (let i = 0; i < arr.length; i++) for (let j = 0; j < arr.length; j++) { } // O(n²)}// Total: O(n²) — termo dominanteLoop interno com 10 iterações fixas → O(n × 10) = O(n).
seção
| Método | Big O |
|---|---|
push, pop | O(1) |
shift, unshift | O(n) |
indexOf, includes, find | O(n) |
map, filter, forEach | O(n) |
sort() | O(n log n) — TimSort no V8 |
Set.has() O(1) vs Array.includes() O(n) — para múltiplas buscas, converta para Set.
seção
Linear — O(n):
function linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) if (arr[i] === target) return i; return -1;}Binária — O(log n) — requer array ordenado:
function binarySearch(arr, target) { let left = 0, 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;}Muitas buscas? Ordene uma vez O(n log n) + binárias O(log n) cada.
seção
| Algoritmo | Pior | Espaço | Uso |
|---|---|---|---|
| Bubble sort | O(n²) | O(1) | Só ensino |
| Merge sort | O(n log n) | O(n) | Garantido |
| Quick sort | O(n²)* | O(log n) | Geral |
JS sort() | O(n log n) | O(n) | Produção |
function bubbleSort(arr) { const r = [...arr]; for (let i = 0; i < r.length; i++) { let swapped = false; for (let j = 0; j < r.length - i - 1; j++) { if (r[j] > r[j + 1]) { [r[j], r[j + 1]] = [r[j + 1], r[j]]; swapped = true; } } if (!swapped) break; } return r;}Na prática: [...arr].sort((a, b) => a - b) — implemente merge sort para aprender, não para prod.
seção
Dois índices em array ordenado — par que soma target:
function twoSumSorted(arr, target) { let left = 0, right = arr.length - 1; while (left < right) { const sum = arr[left] + arr[right]; if (sum === target) return [left, right]; if (sum < target) left++; else right--; } return null;}Soma pequena → move left (valor maior). Soma grande → move right.
seção
Janela deslizante — soma máxima de k consecutivos:
function maxSumSubarray(arr, k) { let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0); let maxSum = windowSum; for (let i = k; i < arr.length; i++) { windowSum = windowSum - arr[i - k] + arr[i]; maxSum = Math.max(maxSum, windowSum); } return maxSum;}Recalcular do zero seria O(n × k); slide é O(n).
Substring única mais longa também usa sliding window + Set.
seção
Contagem com Map/Object evita O(n²):
function isAnagram(a, b) { if (a.length !== b.length) return false; const freq = {}; for (const c of a) freq[c] = (freq[c] || 0) + 1; for (const c of b) { if (!freq[c]) return false; freq[c]--; } return true;}Duplicatas em O(n):
function hasDuplicates(arr) { const seen = new Set(); for (const item of arr) if (seen.has(item)) return true; else seen.add(item); return false;}seção
Set/Map para O(1) lookup → O(n) espaço extra.
Loops aninhados → O(n²) tempo, O(1) espaço extra.
Escolha o trade-off certo para o tamanho do input e memória disponível.
seção
seção
seção
Você avançou na trilha Advanced Topics — sétimo de nove conceitos avançados.
Aplique Big O junto de Data Structures ao escolher Map vs array e Recursion em merge sort e travessias.
→ Design Patterns — modelos de solução reutilizáveis
Fonte de referência: 33jsconcepts.com/concepts/algorithms-big-o ⬀