Big-O descreve como o tempo de execução ou a memória de um algoritmo crescem conforme o tamanho da entrada n cresce. Captura o comportamento assintótico do worst-case, ignorando constantes e termos de ordem inferior.
Nos importamos com a taxa de crescimento, não com contagens exatas de passos. O(2n + 5) é simplesmente O(n) porque conforme n fica grande, constantes e termos menores deixam de importar.
| Big-O | Nome | Exemplo |
|---|
| O(1) | constante | array index lookup |
| O(log n) | logarítmico | binary search |
| O(n) | linear | varredura de uma lista |
| O(n log n) | linearítmico | merge sort |
| O(n²) | quadrático | loops aninhados |
| O(2ⁿ) | exponencial | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O esconde constantes: um algoritmo O(n) com uma constante enorme pode perder para O(n log n) em entradas pequenas. Também rastreie a complexidade de space, não apenas time.
Big-O permite comparar algoritmos sem executá-los ou se preocupar com hardware.
Prevê quais soluções sobrevivem quando as entradas crescem de centenas para milhões — a diferença entre um recurso que escala e um que faz timeout.
É o vocabulário que todo engenheiro usa para raciocinar sobre desempenho.