Big O Notation: O Que A-Level CS Realmente Espera

Big O notation aparece em todos os principais specs de A-level computer science (AQA, OCR, Edexcel) e confunde muitos alunos não porque a matemática seja difícil, mas porque nunca veem isso conectado a código de verdade. Este é um guia prático do que você precisa saber e como responder perguntas de exame sobre isso sem enrolação.

O que Big O realmente mede

Big O descreve como o tempo de execução (ou uso de memória) de um algoritmo cresce conforme o tamanho da entrada, geralmente chamado de n, aumenta. Não é uma medição de cronômetro em segundos. É uma forma de descrever taxa de crescimento para que você possa comparar algoritmos independentemente do hardware.

Quando você escreve O(n), está dizendo: se eu dobrar a entrada, o trabalho aproximadamente dobra. O(n²) significa que dobrar a entrada aproximadamente quadruplica o trabalho. Essa relação é o que os examinadores querem que você identifique, não contagens exatas de operações.

As complexidades que você precisa dominar

Para A-level, estas são as que aparecem repetidamente:

• O(1) – tempo constante. Acessar um elemento de array por índice: arr[5]. Não importa o tamanho do array.
• O(log n) – logarítmica. Binary search em uma lista ordenada. Cada passo reduz pela metade o espaço de busca restante.
• O(n) – linear. Um único loop através de uma lista, como uma busca linear verificando cada item uma vez.
• O(n log n) – linearítmica. Merge sort e quicksort (caso médio) caem aqui.
• O(n²) – quadrática. Loops aninhados sobre os mesmos dados, que é exatamente o que bubble sort, insertion sort e selection sort fazem.
• O(2ⁿ) – exponencial. Fibonacci recursivo ingênuo sem memoização. Fica feio rápido.

Você deve conseguir olhar para pseudocódigo e dizer qual é à primeira vista, porque é basicamente o que é testado.

Lendo código para complexidade

O método que funciona sempre: conte os loops e veja como se relacionam com n.

# O(n) - um loop, uma passagem
for i in range(n):
    print(i)

# O(n^2) - loop aninhado, ambos ligados a n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - o espaço de busca reduz pela metade a cada iteração
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Um loop aninhado onde o intervalo do loop interno depende de n ainda é O(n²), mesmo que pareça ligeiramente diferente (como for j in range(i) em vez de for j in range(n) — ainda é quadrático no geral, só com uma diferença de fator constante).

Tenha cuidado com loops que não dependem de n em absoluto. Um loop que sempre roda 10 vezes independentemente do tamanho da entrada é O(1), mesmo que haja um loop presente. Examinadores gostam de meter isso sorrateiramente.

Algoritmos de ordenação comuns e seu Big O

Este é um tópico favorito de exame porque combina dois specs de uma vez: algoritmos de ordenação e complexidade.

Algoritmo	Melhor caso	Pior caso
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

A consistência do merge sort (mesma complexidade em melhor e pior caso) vale a pena mencionar explicitamente se uma pergunta pedir por que você o escolheria sobre bubble sort para grandes conjuntos de dados. O melhor caso do bubble sort de O(n) só se aplica com uma otimização de saída antecipada quando nenhuma troca acontece em uma passagem — mencione esse detalhe se você trazê-lo à tona, já que alguns exam boards esperam isso.

Onde alunos perdem pontos

O maior: escrever