Skip to main content

BIG-O

  • BIG-O
info

BIG-O explica como o algoritmo escala baseado em uma entrada. Não é sobre performance

Mede a complexidade TEMPORAL(tempo) e ESPACIAL(memória)

danger

As notações abaixo vale para tempo e memória

warning

Sempre considerar o lado pessimista do Algoritmo

Notações​

O(1)​

  • O(1) – Tempo Constante: O desempenho não muda, independentemente do tamanho da entrada. Exemplo: acessar um elemento em um array pelo índice.

O(n)​

  • O(n) – Tempo Linear: O tempo aumenta proporcionalmente ao tamanho da entrada. Exemplo: percorrer e somar todos os elementos de uma lista.

O(n²)​

  • O(n²) – Tempo Quadrático: O tempo aumenta com o quadrado do tamanho da entrada. Exemplo: verificar cada par, cada permutação, de elementos em uma lista (como em Bubble Sort). É um loop dentro de um loop

O(n log n)​

  • O(n log n) – Tempo Log-linear: Comum em algoritmos eficientes de ordenação, como Merge Sort, ou outros algoritmos de divide and conquer.

O(log n)​

  • O(log n) – Tempo Logarítmico: O tempo aumenta logaritmicamente à medida que a entrada cresce. Exemplo: binary search.

    📈 Explicação

    Tamanho do input nTempo em O(n)Tempo em O(log n)
    1010~3.3
    2020~4.3
    4040~5.3

    Veja que quando o input dobra de 10 para 20, o tempo em O(log n) só aumenta de ~3.3 para ~4.3.

    ✅ Uma forma correta de descrever O(log n) seria:

    "Se o input dobra, o tempo de execução aumenta um pouco, seguindo um crescimento logarítmico."