Ler notação Big-O: o que O(n log n) diz na prática
Pergunta
O que a notação Big-O descreve, e o que significa dizer que um algoritmo é O(n log n) em vez de O(n²)?
Resposta esperada
Big-O descreve como o custo (tempo ou espaço) cresce em função do tamanho da entrada, ignorando constantes e termos menores — é sobre a forma da curva, não o tempo absoluto. O(n²) dobra de custo quatro vezes quando a entrada dobra; O(n log n) dobra pouco mais que o dobro. Na prática: para 1.000 itens, n² são ~1 milhão de operações e n log n são ~10 mil — a diferença deixa de ser acadêmica assim que a entrada cresce. Ordenações eficientes (merge sort, quicksort médio) são O(n log n); o loop aninhado ingênuo costuma ser O(n²).
Por que perguntam isso
A resposta fraca recita a definição sem conseguir dar um número. Peça uma estimativa concreta ('quantas operações pra n = 1000?') — quem entende de verdade responde na hora.