A notação Big O descreve como o trabalho cresce conforme a entrada cresce, ignorando fatores constantes:
- O(1): o mesmo trabalho para qualquer tamanho, como uma consulta em um dicionário ou conjunto.
- O(n): uma passada pelos dados.
- O(n log n): ordenação.
- O(n²): um loop dentro de outro loop sobre os mesmos dados. Dez vezes mais linhas significam cem vezes mais trabalho.
Alguns loops se escondem em uma única linha. x in a_list percorre a lista, então fazer isso para cada item de outra lista é O(n²). x in a_set é O(1) em média, então criar um conjunto uma única vez transforma todo o trabalho em O(n). O mesmo vale para list.index, list.count e list.remove dentro de um loop.
Outro truque é calcular uma vez e reutilizar: totais acumulados respondem a cada pergunta de "soma de i até j" com uma única subtração.
Nesta unidade, as verificações ocultas usam entradas com milhares de itens. Uma resposta quadrática excede o tempo limite mesmo quando está correta com poucos dados.
Saída: ['SO-1']. Cada in no conjunto é um único passo, não uma varredura da lista.