Big-O a través de ejemplos de código: Entiende la complejidad algorítmica fácilmente

1. Descripción general

Big-O es la forma de describir cómo aumenta el tiempo de ejecución (o la memoria) cuando el tamaño de entrada crece. Este artículo no usa fórmulas matemáticas áridas, sino que recorre cada nivel de complejidad común mediante código Java real, con análisis de qué líneas generan el costo. Cuando termines de leerlo, podrás ver un fragmento de código e identificar al instante si es O(1), O(n), O(n log n) u O(n²) sin necesidad de contar con las manos.

2. Big-O, ¿qué es y por qué nos importa?

Big-O responde la pregunta: “Si la entrada se duplica, ¿cuánto aumenta el tiempo de ejecución?” Ignora las constantes y los factores menores, manteniendo solo la tendencia de crecimiento cuando n (el tamaño de entrada) tiende al infinito.

n = 1.000      -> O(n) corre ~1.000 pasos
n = 1.000.000  -> O(n) corre ~1.000.000 pasos (crece linealmente)
n = 1.000.000  -> O(n²) corre ~10^12 pasos (crece extremadamente rápido)

Dos fragmentos de código pueden “verse parecidos a primera vista” pero tener complejidad muy diferente si uno esconde un bucle en una llamada a función. Entender Big-O te ayuda a evitar escribir código que funciona bien con 100 registros de prueba pero “se congela” en producción con 10 millones de registros.

Nota: Big-O describe el peor caso (worst case) según la convención más común, a menos que se especifique best-case o average-case.

3. O(1) – Tiempo constante

El tiempo de ejecución no cambia, sin importar el tamaño de la entrada.

public class InventoryCache {

    private final Map<String, Integer> stockBySku = new HashMap<>();

    public Integer getStock(String sku) {
        return stockBySku.get(sku); // HashMap.get es O(1) en promedio
    }
}

get() en HashMap calcula el hash de la clave y salta directamente al bucket correspondiente, sin depender de la cantidad de elementos en el mapa. De manera similar, acceder a array[i] o list.get(i) con ArrayList también es O(1) porque solo necesita calcular la dirección de offset.

4. O(n) – Tiempo lineal

El tiempo de ejecución aumenta proporcionalmente con el tamaño de la entrada.

public class OrderValidator {

    public boolean hasExpiredItem(List<Order> orders) {
        for (Order order : orders) {
            if (order.isExpired()) {
                return true; // se detiene pronto pero en el peor caso recorre toda la lista
            }
        }
        return false;
    }
}

El bucle for recorre como máximo n elementos de orders. El peor caso ocurre cuando ningún pedido está vencido, obligándote a revisar toda la lista. Este es el patrón O(n) clásico: un bucle simple, sin anidamiento.

4.1. Trampa común: contains() dentro de un bucle

public class DuplicateChecker {

    // O(n²) porque contains() en una List es O(n), ejecutado n veces
    public boolean hasDuplicateSlow(List<String> emails) {
        List<String> seen = new ArrayList<>();
        for (String email : emails) {
            if (seen.contains(email)) {
                return true;
            }
            seen.add(email);
        }
        return false;
    }
}

seen.contains(email) en ArrayList es O(n) porque debe recorrer linealmente para buscar. Llamarla dentro del bucle for convierte toda la función en O(n²) — un error muy fácil de cometer si no prestas atención a la estructura de datos interna.

public class DuplicateChecker {

    // O(n) gracias a que HashSet.add/contains es O(1)
    public boolean hasDuplicateFast(List<String> emails) {
        Set<String> seen = new HashSet<>();
        for (String email : emails) {
            if (!seen.add(email)) { // add() devuelve false si ya existe
                return true;
            }
        }
        return false;
    }
}

Solo cambiando List por HashSet, la complejidad se reduce de O(n²) a O(n). Este es el ejemplo más práctico que muestra que elegir la estructura de datos correcta es más importante que las “micro-optimizaciones”.

5. O(log n) – Tiempo logarítmico

Cada paso descarta la mitad del espacio de búsqueda.

public class PriceLookup {

    // sortedPrices debe estar ordenado en orden ascendente previamente
    public int findIndex(int[] sortedPrices, int target) {
        int low = 0;
        int high = sortedPrices.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (sortedPrices[mid] == target) {
                return mid;
            } else if (sortedPrices[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

La búsqueda binaria divide a la mitad el arreglo en cada iteración while, así que con n = 1.000.000 solo necesita alrededor de 20 pasos (log₂ 1.000.000 ≈ 20) para encontrar el resultado, en lugar de recorrer linealmente un millón de elementos.

class PriceLookupTest {

    @Test
    void shouldFindIndexInSortedArray() {
        int[] prices = {10, 20, 30, 40, 50};
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(prices, 40);

        assertThat(index).isEqualTo(3);
    }

    @Test
    void shouldReturnMinusOneWhenNotFound() {
        PriceLookup lookup = new PriceLookup();

        int index = lookup.findIndex(new int[] {1, 2, 3}, 99);

        assertThat(index).isEqualTo(-1);
    }
}

Esta prueba confirma el comportamiento correcto tanto cuando se encuentra (devuelve el índice) como cuando no se encuentra (devuelve -1), las dos ramas más importantes de la búsqueda binaria.

6. O(n log n) – Combinación de lineal y logarítmico

Esta es la complejidad de los algoritmos de ordenamiento eficientes como merge sort, quick sort (caso promedio), o Collections.sort().

public class RevenueReport {

    public List<Order> sortByAmountDescending(List<Order> orders) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
        return copy;
    }
}

Collections.sort()/List.sort() en Java usa Timsort (una variante de merge sort), garantizando O(n log n) en el peor caso. Si ves código que llama a sort() dentro de un bucle que se ejecuta n veces, la complejidad total se multiplica a O(n² log n) — una señal de que necesitas refactorizar.

7. O(n²) – Tiempo cuadrático

Dos bucles anidados, cada uno recorriendo la totalidad (o casi) de la entrada.

public class PairFinder {

    // Encuentra todos los pares de productos cuya suma de precios es igual al objetivo
    public List<int[]> findPairsSlow(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] + prices[j] == target) {
                    result.add(new int[] {prices[i], prices[j]});
                }
            }
        }
        return result;
    }
}

El bucle externo se ejecuta n veces, el bucle interno se ejecuta hasta n veces por cada iteración del bucle externo — el número total de comparaciones es aproximadamente n²/2, así que la complejidad es O(n²). Con n = 10.000, son 50 millones de comparaciones — funciona pero se nota claramente la lentitud.

public class PairFinder {

    // O(n) gracias a HashSet que guarda los valores ya vistos
    public List<int[]> findPairsFast(int[] prices, int target) {
        List<int[]> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int price : prices) {
            int complement = target - price;
            if (seen.contains(complement)) {
                result.add(new int[] {complement, price});
            }
            seen.add(price);
        }
        return result;
    }
}

En lugar de comparar cada par, solo necesitamos un bucle y una búsqueda O(1) en HashSet. Esta es la técnica muy común de “intercambiar tiempo por memoria”: usamos más espacio para almacenar seen, pero reducimos la complejidad de O(n²) a O(n).

8. O(2^n) – Tiempo exponencial

El tiempo de ejecución se duplica cada vez que la entrada aumenta en 1 — comúnmente se ve en funciones recursivas que calculan todos los subconjuntos.

public class SubsetGenerator {

    public List<List<Integer>> generateAllSubsets(List<Integer> items) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(items, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(List<Integer> items, int index,
                            List<Integer> current, List<List<Integer>> result) {
        if (index == items.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Rama 1: no seleccionar item[index]
        backtrack(items, index + 1, current, result);

        // Rama 2: seleccionar item[index]
        current.add(items.get(index));
        backtrack(items, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Cada elemento crea 2 ramas recursivas (seleccionar o no), así que con n elementos tenemos 2^n subconjuntos. Con n = 20, ya hay más de 1 millón de subconjuntos; con n = 40, ninguna máquina lo terminará en tiempo razonable. Esta es una señal de que debes considerar usar programación dinámica (dynamic programming) si el problema lo permite.

9. Comparación rápida con benchmark real

Un ejemplo de prueba simple para “ver” la diferencia entre O(n) y O(n²):

class DuplicateCheckerBenchmarkTest {

    @Test
    void fastVersionShouldHandleLargeInputQuickly() {
        List<String> emails = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) {
            emails.add("user" + i + "@example.com");
        }
        DuplicateChecker checker = new DuplicateChecker();

        long start = System.nanoTime();
        boolean hasDuplicate = checker.hasDuplicateFast(emails);
        long elapsedMs = (System.nanoTime() - start) / 1_000_000;

        assertThat(hasDuplicate).isFalse();
        assertThat(elapsedMs).isLessThan(500); // O(n) así que sigue siendo muy rápido con 100k elementos
    }
}

Si reemplazas hasDuplicateFast con hasDuplicateSlow con los mismos 100.000 emails, el tiempo de ejecución superará ampliamente los 500ms — prueba visual clara de la diferencia entre O(n) y O(n²) con datos reales.

10. Tabla de resumen y reglas de identificación rápida

Big-O	Indicios en el código	Ejemplo
O(1)	Sin bucles, acceso directo (índice de array, HashMap.get)	map.get(key)
O(log n)	Cada paso descarta una parte del espacio de búsqueda	Búsqueda binaria
O(n)	Un bucle simple recorriendo la entrada	for sobre List
O(n log n)	Bucle combinado con sort, o divide-and-conquer	Collections.sort()
O(n²)	Bucle anidado dentro de bucle, ambos recorriendo la entrada	Comparar cada par
O(2^n)	Recursión con 2 ramas en cada paso, sin poda	Generar todos los subconjuntos

Regla de conteo rápido: cuenta los bucles anidados que recorren la entrada — cada nivel de bucle añade un “grado n”. Si dentro del bucle llamas funciones de librería (contains, sort, indexOf), consulta la complejidad de esa función antes de sumarla al total.

Nota: Big-O no dice nada sobre las constantes reales. Un algoritmo O(n) con una constante grande (por ejemplo, leer un archivo en cada iteración) puede ser más lento que O(n log n) con una constante pequeña cuando n aún no es lo suficientemente grande. No optimices Big-O a ciegas sin perfilar (profile) el código real.

11. Conclusión

Big-O es una herramienta para predecir tendencias, no un número absoluto — pero esa tendencia es lo que decide si tu código sobrevive o colapsa cuando los datos crecen. El consejo más práctico: cada vez que escribas un bucle, pregúntate “¿llamo alguna función O(n) dentro de este bucle?” — esa es la fuente de la mayoría de errores O(n²) no deseados en la práctica. Dominar los 6 niveles de complejidad anteriores es suficiente para entender y cuestionar la mayoría del código algorítmico que encuentras a diario.