Big-O: complexidade de tempo e espaço

O que o Big-O mede

Big-O descreve como o custo de um algoritmo cresce quando a entrada (n) cresce, ignorando constantes e detalhes da máquina. Não diz "quantos milissegundos", e sim "se dobrar a entrada, o que acontece": em O(n) o tempo dobra, em O(n²) quadruplica, em O(log n) aumenta um passo só.

Como calcular

• Laços em sequência somam: O(n) + O(n) = O(n).
• Laços aninhados multiplicam: um laço de n dentro de outro de n é O(n²).
• Dividir pela metade a cada passo dá O(log n) (busca binária).
• Fique com o termo dominante e descarte constantes: O(3n² + 5n + 100) = O(n²).

Pior caso, caso médio e espaço

Normalmente falamos do pior caso (a garantia). Às vezes o caso médio importa mais: tabela hash é O(1) em média e O(n) no pior caso. Big-O também mede memória extra — uma cópia do array custa O(n) de espaço, um contador custa O(1).

// O(n²): compara cada item com todos os outros
fun temRepetido(ids: List<Int>): Boolean {
    for (i in ids.indices)
        for (j in i + 1 until ids.size)
            if (ids[i] == ids[j]) return true
    return false
}

// O(n) de tempo e O(n) de espaço: um conjunto lembra o que já passou
fun temRepetido(ids: List<Int>): Boolean {
    val vistos = HashSet<Int>()
    for (id in ids) if (!vistos.add(id)) return true
    return false
}