Definição completa
Big O é uma notação matemática usada para descrever o comportamento de um algoritmo conforme o tamanho da entrada (n) cresce. Representa o pior caso de tempo ou memória necessária. As complexidades mais comuns são: O(1) constante, O(log n) logarítmica, O(n) linear, O(n log n) log-linear, O(n²) quadrática e O(2ⁿ) exponencial. Entender Big O é essencial para escolher algoritmos e estruturas de dados adequados para cada problema.
Exemplo de código
// Exemplos de complexidades diferentes
// O(1) — acesso direto por índice
const primeiro = array[0];
// O(n) — percorre todos os elementos
const encontrado = array.find(x => x === alvo);
// O(n²) — loop aninhado (evitar em grandes datasets)
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// executa n * n vezes
}
}
// O(log n) — busca binária (array ordenado)
function buscaBinaria(arr, alvo) {
let inicio = 0, fim = arr.length - 1;
while (inicio <= fim) {
const meio = Math.floor((inicio + fim) / 2);
if (arr[meio] === alvo) return meio;
arr[meio] < alvo ? inicio = meio + 1 : fim = meio - 1;
}
return -1;
}