O que é Big-O?

Introdução ao Big-O

Complexidade de um algoritmo diz respeito à escalabilidade - como o algoritmo se comporta conforme aumentamos o tamanho de dados.

Quando falamos de complexidade, respondemos: O quão bem (ou mal) esse algoritmo escala quando dados crescem?

Não é sobre velocidade ou tempo de execução - é uma forma de analisar eficiência independente de hardware ou linguagem. A diferença entre Bubble Sort e Quick Sort é irrelevante com 10 elementos, mas gritante com 1 milhão.

Por que não medir tempo real?

Existem dois tipos de medida: tempo real e tempo assintótico.

Tempo real:

• Mede tempo exato de execução em milissegundos
• Varia conforme CPU, cache, temperatura e fatores externos
• Não é confiável

Tempo assintótico:

• Medida matemática do crescimento de operações
• Focado no comportamento conforme entrada cresce
• Ignora fatores externos (hardware, linguagem)
• É a métrica que importa

function copiarArray(lista: number[]) {
	const copia = [];
	for (let item of lista) {
		copia.push(item);
	}
	return copia;
}

Complexidade espacial: O(n)

Lembre: Big-O sempre considera o pior caso.

Principais Complexidades

Detalhando as complexidades mais importantes e usadas em entrevistas técnicas.

O(1) - Constante

O(1) significa operações que não dependem do tamanho de entrada n. Exemplos: leitura de valor em hash table, acesso ao array por índice.

const x = arr[10];

O(n) - Linear

O(n) significa operações que crescem proporcionalmente ao tamanho n. Se n dobra, custo dobra.

Somar valores do array:

function soma(arr: number[]): number {
	let total = 0;
	for (let i = 0; i < arr.length; i++) {
		total += arr[i];
	}
	return total;
}

Cada elemento é visitado uma vez → O(n)

Busca linear:

function inclui(arr: number[], alvo: number) {
	for (let x of arr) {
		if (x === alvo) return true;
	}
	return false;
}

Pior caso: percorre todos n elementos → O(n)

O(n²) - Quadrática

O(n²) descreve operações que crescem ao quadrado. Se n dobra, operações quadruplicam. Típico de loops aninhados:

for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++) {
		// ...
	}
}

Exemplos: Bubble Sort, Selection Sort, Insertion Sort

O(log n) - Logarítmica

O(log n) cresce muito lentamente conforme n aumenta. Exemplo clássico: busca binária em array de 1.000.000 elementos precisa apenas ~20 passos!

log₂(1.000.000) ≈ 20

function buscaBinaria(arr: number[], alvo: number): number {
	let esquerda = 0;
	let direita = arr.length - 1;

	while (esquerda <= direita) {
		const meio = Math.floor((esquerda + direita) / 2);
		if (arr[meio] === alvo) {
			return meio;
		} else if (arr[meio] < alvo) {
			esquerda = meio + 1;
		} else {
			direita = meio - 1;
		}
	}
	return null;
}

A cada iteração, reduz pela metade os elementos restantes → operações ∝ log(n)

Conclusão

Big-O é conceito fundamental para qualquer desenvolvedor que queira entender algoritmos, estruturas de dados e tomar decisões arquiteturais informadas. Cai frequentemente em entrevistas técnicas e é essencial para código que escala bem.