Estimador de Complexidade

Selecione padrões de código comuns para estimar a complexidade assintótica.

Padrão de Código

Valor de n n = 100

Pseudocódigo

para i = 1 até n:
    operação O(1)

💡

O que significa um valor grande na notação O?

Quanto maior o valor dentro do O(...), mais o número de operações dispara conforme n cresce.

O(1) e O(log n): extremamente rápidos — mesmo com n enorme, o trabalho quase não aumenta.
O(n): aceitável — dobra de trabalho para cada dobra de n.
O(n log n): bom — usado nos melhores algoritmos de ordenação.
O(n²) e O(n³): pesados — com n = 1000, são milhões ou bilhões de operações.
O(2ⁿ) e O(n!): impraticáveis — com n > 30 ou n > 10, o tempo torna-se inviável.

Use o Comparador acima para visualizar graficamente como cada função cresce.

Compare múltiplas funções de complexidade para diferentes valores de n.

📐

Máximo n

n = 1000

📈

📋

Função	n = 1	n = 10	n = 100	n = 1000

Classes de complexidade e exemplos clássicos.

📚

Notação	Nome	Exemplo
`O(1)`	Constante	Acesso por índice em array
`O(log n)`	Logarítmica	Busca binária
`O(n)`	Linear	Busca linear, loop simples
`O(n log n)`	Linearítmica	Merge Sort, Quick Sort (médio)
`O(n²)`	Quadrática	Bubble Sort, loops aninhados
`O(2ⁿ)`	Exponencial	Problema do caixeiro viajante (força bruta)
`O(n!)`	Fatorial	Permutações completas

❓

Em Análise de Algoritmos, log significa logaritmo binário (base 2), não logaritmo decimal. A razão:

A maioria dos algoritmos analisados divide o problema ao meio (busca binária, merge sort), e cada divisão corresponde a multiplicar por log₂.
Em Big-O, a base do logaritmo é irrelevante — logₐ n e log_b n diferem apenas por uma constante multiplicativa, e constantes são ignoradas na notação O.
Por convenção da Ciência da Computação, escrevemos apenas log n subentendendo base 2, simplificando a notação sem perda de precisão.