Introducción a la Complejidad

Cuando comparamos dos algoritmos que resuelven el mismo problema, no nos interesa cuántos segundos tarda cada uno en una computadora específica. Nos interesa cómo crece el tiempo cuando el input se hace más grande. Esa pregunta tiene una respuesta independiente del hardware: la complejidad asintótica.

El experimento mental

Imagina dos funciones que buscan un número en una lista de N elementos:

• La primera recorre toda la lista comparando elemento por elemento.
• La segunda asume que la lista está ordenada y aplica búsqueda binaria.

Para N = 100, ambas son instantáneas. Para N = 1.000.000, la primera hace en promedio 500.000 comparaciones, la segunda hace 20. Esa diferencia escala: para N = 1.000.000.000 la primera hace 500 millones, la segunda hace 30.

La complejidad es la forma de describir esa diferencia sin medir el reloj.

Big O

O(f(n)) describe el crecimiento del tiempo o memoria como función del tamaño del input n. Las complejidades más comunes:

Notación	Nombre	Ejemplo
O(1)	constante	Acceder a arr[i]
O(log n)	logarítmica	Búsqueda binaria
O(n)	lineal	Recorrer un arreglo
O(n log n)	linearítmica	Ordenamientos eficientes (merge sort, heap sort)
O(n²)	cuadrática	Dos loops anidados sobre el arreglo
O(2^n)	exponencial	Generar todos los subconjuntos
O(n!)	factorial	Generar todas las permutaciones

Para N = 1.000.000:

• O(1) → 1 operación
• O(log n) → 20 operaciones
• O(n) → 1.000.000 operaciones
• O(n log n) → 20.000.000 operaciones
• O(n²) → 1.000.000.000.000 operaciones (años en una computadora)
• O(2^n) → más operaciones que átomos en el universo observable

La diferencia entre O(n²) y O(n log n) puede ser entre "termina en un segundo" y "no termina nunca".

Las dos reglas para calcular Big O

Regla 1: descartar constantes. O(3n) se escribe O(n). O(n/2) también es O(n). La constante multiplicativa no afecta el crecimiento asintótico.

Regla 2: descartar términos de menor orden. O(n² + n) se escribe O(n²) porque para n grande el término cuadrático domina al lineal.

Cómo se mide en código

Cuento operaciones básicas (asignaciones, comparaciones, accesos a memoria) y veo cómo crecen con n.

def es_par(n):
    return n % 2 == 0

Una operación: módulo y comparación. No depende de nada que crezca. Es O(1).

def suma(arr):
    total = 0
    for x in arr:
        total += x
    return total

El loop corre n veces donde n = len(arr). Cada iteración hace una operación constante. Total: O(n).

def tiene_duplicado(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

Dos loops anidados. En el peor caso, el interno corre n + (n-1) + (n-2) + ... + 1 ≈ n²/2 veces. Total: O(n²).

Peor caso, mejor caso, caso promedio

Big O describe casi siempre el peor caso porque es la única garantía sólida.

En tiene_duplicado, si los dos primeros elementos son iguales, el mejor caso es O(1). El peor caso (no hay duplicados) es O(n²). En entrevistas y análisis serios, asume peor caso salvo que te pidan otro escenario explícitamente.

Espacio: memoria, no tiempo

Big O también se aplica a memoria. Un algoritmo es O(1) en espacio si usa una cantidad fija de variables sin importar n. Es O(n) en espacio si crea una estructura proporcional al input (un arreglo nuevo, un diccionario, recursión que apila n marcos).

Cuando un problema dice "resuelve in-place" suele significar "usa O(1) espacio extra".

Por qué importa todo esto

En entrevistas técnicas, "¿qué complejidad tiene tu solución?" es la primera pregunta después de que el código funciona. No saber responderla descalifica.

En producción, la diferencia entre O(n²) y O(n log n) es lo que separa una página que carga en 100ms de una que tarda 10 segundos cuando los datos crecen.

Lo que practicas en este tema

1. Análisis amortizado: cuándo una operación cara se compensa con muchas baratas.
2. Master theorem: la herramienta para algoritmos recursivos divide-y-vencerás.
3. Trade-offs tiempo vs espacio: gastar memoria para ganar tiempo, y viceversa.
4. Casos prácticos: cómo justificar la complejidad de cualquier código en una entrevista.

Después, cada tema del curso indica la complejidad de los problemas. Vas a poder leerla y entender por qué.