Big O Notation: What A-Level CS Actually Expects

La notación Big O aparece en todos los especificados principales de informática A-level (AQA, OCR, Edexcel) y confunde a muchos estudiantes no porque las matemáticas sean difíciles, sino porque nunca la ven vinculada a código real. Esta es una explicación práctica de lo que necesitas saber y cómo responder preguntas de examen sin divagar.

Qué mide realmente Big O

Big O describe cómo crece el tiempo de ejecución (o el uso de memoria) de un algoritmo conforme el tamaño de entrada, usualmente llamado n, se hace más grande. No es una medida en segundos del cronómetro. Es una forma de describir la tasa de crecimiento para que puedas comparar algoritmos independientemente del hardware.

Cuando escribes O(n), estás diciendo: si duplico la entrada, el trabajo se duplica aproximadamente. O(n²) significa que duplicar la entrada hace que el trabajo se cuadruplique aproximadamente. Esa relación es lo que los examinadores quieren que identifiques, no el conteo exacto de operaciones.

Las complejidades que necesitas dominar

Para A-level, estas son las que aparecen una y otra vez:

• O(1) – tiempo constante. Acceder a un elemento de un array por índice: arr[5]. No importa cuán grande sea el array.
• O(log n) – logarítmica. Búsqueda binaria en una lista ordenada. Cada paso reduce a la mitad el espacio de búsqueda restante.
• O(n) – lineal. Un bucle simple a través de una lista, como una búsqueda lineal que verifica cada elemento una sola vez.
• O(n log n) – lineal-logarítmica. Merge sort y quicksort (caso promedio) están aquí.
• O(n²) – cuadrática. Bucles anidados sobre los mismos datos, que es exactamente lo que hacen bubble sort, insertion sort y selection sort.
• O(2ⁿ) – exponencial. Fibonacci recursivo ingenuo sin memoización. Se vuelve feo rápidamente.

Deberías poder mirar pseudocódigo e identificar cuál de estas es a primera vista, porque eso es mayormente lo que se pone a prueba.

Leyendo código para complejidad

El método que funciona siempre: cuenta los bucles y ve cómo se relacionan con n.

# O(n) - un bucle, un recorrido
for i in range(n):
    print(i)

# O(n^2) - bucle anidado, ambos vinculados a n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - el espacio de búsqueda se reduce a la mitad cada iteración
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

Un bucle anidado donde el rango del bucle interno depende de n sigue siendo O(n²), aunque se vea ligeramente diferente (como for j in range(i) en lugar de for j in range(n) — eso sigue siendo cuadrático en general, solo con una diferencia de factor constante).

Cuida los bucles que no dependen de n en absoluto. Un bucle que siempre se ejecuta 10 veces independientemente del tamaño de entrada es O(1), aunque haya un bucle presente. A los examinadores les gusta meter esto en secreto.

Algoritmos de ordenamiento comunes y su Big O

Este es un tema favorito de examen porque combina dos especificados a la vez: algoritmos de ordenamiento y complejidad.

Algoritmo	Mejor caso	Peor 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)

La consistencia de merge sort (misma complejidad en mejor y peor caso) vale la pena mencionar explícitamente si una pregunta pide por qué lo elegirías sobre bubble sort para conjuntos de datos grandes. El mejor caso O(n) de bubble sort solo se aplica con una optimización de salida anticipada cuando no hay intercambios en un recorrido — menciona ese detalle si lo sacas a colación, ya que algunos tribunales de examen lo esperan.

Dónde los estudiantes pierden puntos

El más grande: escribir