Sua solução funciona. Passa nos testes. Mas quando os dados crescem de 100 para 100.000 registros, ela trava. Você não entende por quê — o código está certo. O problema não é correção, é performance, e para analisar performance precisamos de uma linguagem comum: a Big O Notation. É o vocabulário que todo desenvolvedor precisa para discutir eficiência de algoritmos e não ficar na mão quando os dados crescem.
O que Big O mede
Big O descreve como o tempo de execução (ou uso de memória) de um algoritmo cresce em função do tamanho dos dados de entrada (n). Não mede tempo em segundos — isso depende do hardware, da linguagem, do compilador. Mede a taxa de crescimento: O(1) cresce constante (não importa o n), O(n) cresce linearmente, O(n²) cresce quadraticamente. Compara algoritmos de forma independente de hardware — um O(n) é sempre mais escalável que O(n²) para n suficientemente grande.
A notação ignora constantes e termos menores: O(2n) e O(n + 100) são ambos O(n). Isso pode parecer impreciso, mas na prática para grandes n, a constante importa muito menos que a ordem de crescimento. O que importa é: dobrar n, quanto o algoritmo demora mais? Linear (2x)? Quadrático (4x)? Logarítmico (apenas um pouco mais)?
O(1) — Tempo constante
A operação leva o mesmo tempo independente do n. Acessar um elemento de um array pelo índice (arr[500]) é O(1) — não importa se o array tem 10 ou 10 milhões de elementos, é uma operação de memória direta. Inserção/deleção no início ou fim de certas estruturas de dados também é O(1). Has tables (dicionários, objetos JavaScript, HashMaps Java) têm acesso por chave O(1) em média — muito mais rápido que buscar em um array não ordenado.
O(log n) — Tempo logarítmico
A log base 2 de 1 milhão é apenas 20. Isso significa que um algoritmo O(log n) resolve 1 milhão de elementos em 20 “passos”. O exemplo mais claro é a busca binária: em um array ordenado, você compara o elemento do meio, descarta metade do array, e repete. Cada passo elimina metade da busca. Para 1 bilhão de elementos, a busca binária precisa de no máximo 30 comparações. Algoritmos O(log n) são praticamente constantes na prática para qualquer tamanho de dado razoável.
O(n) — Tempo linear
O tempo cresce proporcionalmente ao n. Percorrer um array do início ao fim para encontrar o maior elemento é O(n) — você precisa olhar cada elemento uma vez. Duplicar n dobra o tempo. Linear é geralmente considerado eficiente para operações que precisam processar cada elemento. A maioria dos algoritmos de streaming de dados e processamento de logs é O(n) — você lê cada registro uma vez e o descarta.
O(n log n) — Quase linear
É a complexidade dos melhores algoritmos de ordenação genéricos (Merge Sort, Quick Sort em média, Heap Sort, Timsort). É levemente pior que linear mas muito melhor que quadrático. Para 1 milhão de elementos: O(n) faz 1M operações, O(n log n) faz ~20M, O(n²) faz 1 trilhão. Na prática, O(n log n) é considerado ótimo para algoritmos de ordenação — e foi provado matematicamente que nenhum algoritmo baseado em comparações pode superar O(n log n).
O(n²) — Tempo quadrático e pior
Dois loops aninhados que percorrem o mesmo array geralmente geram O(n²). Para 1000 elementos, são 1 milhão de operações. Para 10.000, são 100 milhões. Para 100.000, são 10 bilhões — começa a ficar impraticável. Bubble Sort, Insertion Sort e Selection Sort são O(n²). Algoritmos O(n³) (três loops aninhados) são raros em uso prático por serem proibitivos. Multiplicação de matrizes ingênua é O(n³).
O(2^n) e O(n!) crescem de forma explosiva — impraticáveis para n acima de 20-30. Aparecem em problemas combinatoriais como o problema do caixeiro viajante (brute force). Para esses problemas, algoritmos de aproximação ou heurísticas são a solução prática. Internalizar Big O muda como você escreve código: antes de escolher uma estrutura de dados, você pergunta “que operações vou fazer mais e qual é a complexidade delas?”. Um HashMap em vez de uma busca linear pode ser a diferença entre uma aplicação que serve 100 usuários e uma que serve 1 milhão.
Tem um projeto em mente?
Somos especialistas em transformar ideias em produtos digitais. Apps, sites, automações e IA — vamos construir juntos.
