Complejidad y notación Big-O

📐 Fundamento

Big-O ($O$) — cota superior

$f(n) = O(g(n))$ si existe $c > 0$ y $n_0$ tales que $f(n) \leq c \cdot g(n)$ para todo $n \geq n_0$.

En palabras: $f$ no crece más rápido que $g$ (a la larga, ignorando constantes).

Ejemplos:

• $3n + 5 = O(n)$. (Para $n$ grande, $3n$ domina al 5; constante 3 se ignora.)
• $n^2 + 100n = O(n^2)$. (Para $n$ grande, $n^2$ domina.)
• $5 \log n = O(\log n)$.
• $1000 = O(1)$. (Una constante es $O(1)$.)
• $n = O(n^2)$. (Sí — porque $n$ no crece más rápido que $n^2$. Big-O da una cota superior, no necesariamente apretada.)

Big-Omega ($\Omega$) — cota inferior

$f(n) = \Omega(g(n))$ si $f(n) \geq c \cdot g(n)$ para $n$ grande.

En palabras: $f$ crece al menos tan rápido como $g$.

Big-Theta ($\Theta$) — cota apretada

$f(n) = \Theta(g(n))$ si $f$ es a la vez $O(g)$ y $\Omega(g)$.

En palabras: $f$ y $g$ crecen al mismo orden.

En la práctica casi siempre decimos "Big-O" aunque queramos decir Big-Theta. No es 100% formal pero la convención es así.

Reglas para simplificar

1. Constantes se ignoran. $5n^3 \to n^3$.
2. Términos no dominantes se ignoran. $n^2 + n \to n^2$.
3. El término más rápido manda. $\log n + n \to n$.

Jerarquía común (de más rápido a más lento):

📐 Fundamento

$O(1)$ — Constante

No depende del tamaño. Acceso directo, lookup en hash, asignación.

def primero(lista):
    return lista[0]      # O(1) sin importar el tamaño

$O(\log n)$ — Logarítmica

Cada paso reduce el problema a la mitad. Búsqueda binaria, operaciones en árboles balanceados, exponenciación rápida.

def buscar_binario(lista, x):    # O(log n)
    lo, hi = 0, len(lista) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if lista[mid] == x: return mid
        if lista[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

Para $n = 10^9$, $\log_2 n \approx 30$. 30 comparaciones para 1000 millones. Mágico.

$O(n)$ — Lineal

Una pasada por los datos. Búsqueda lineal, suma, máximo.

def maximo(lista):       # O(n)
    m = lista[0]
    for x in lista[1:]:
        if x > m: m = x
    return m

$O(n \log n)$ — Cuasi-lineal

Algoritmos de ordenamiento eficientes (mergesort, heapsort, Timsort). Es el mejor caso para ordenamiento por comparación.

sorted(lista)            # O(n log n) en promedio

$O(n^2)$ — Cuadrática

Bucle anidado. Algoritmos simples de ordenamiento (bubble, selection, insertion).

def ordenamiento_burbuja(lista):     # O(n²)
    n = len(lista)
    for i in range(n):
        for j in range(n - i - 1):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]

Para $n = 10^4$, $n^2 = 10^8$. Lento pero manejable. Para $n = 10^6$, inviable.

$O(2^n)$ — Exponencial

Cada elemento duplica el trabajo. Subsets, recursión sin memoización (Fibonacci ingenuo), backtracking sin podas.

def fib(n):              # O(2^n)
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Para $n = 40$, ya tarda segundos. Para $n = 60$, siglos.

$O(n!)$ — Factorial

Permutaciones. Algoritmos de fuerza bruta sobre todas las combinaciones.

Para $n = 12$, ya estás en mil millones. Para $n = 20$, totalmente inviable.

Comparación visual

📐 Fundamento

Bucle simple

for i in range(n):
    op_constante()
# Total: O(n)

$n$ iteraciones, cada una $O(1)$. Total: $O(n)$.

Bucle anidado

for i in range(n):
    for j in range(n):
        op_constante()
# Total: O(n²)

$n \cdot n = n^2$ ejecuciones.

Bucle con paso variable

i = 1
while i < n:
    op_constante()
    i *= 2
# Total: O(log n)

$i$ duplica cada paso → $\log_2 n$ iteraciones.

Bucle dependiente

for i in range(n):
    for j in range(i):
        op_constante()

Total: $0 + 1 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2} = O(n^2)$.

Recursión

Para una recursión con $a$ llamadas que reducen el problema a tamaño $n/b$ con $O(n^d)$ trabajo extra, el Teorema Maestro dice:

Ejemplos:

• Búsqueda binaria: $T(n) = T(n/2) + O(1)$. $a=1, b=2, d=0$. Caso $a = b^d$ → $O(\log n)$.
• Mergesort: $T(n) = 2T(n/2) + O(n)$. $a=2, b=2, d=1$. Caso $a = b^d$ → $O(n \log n)$.
• Karatsuba (multiplicación): $T(n) = 3T(n/2) + O(n)$. $a > b^d$ → $O(n^{\log_2 3}) \approx O(n^{1.58})$.

Análisis amortizado

A veces una operación parece cara pero en promedio es barata.

Ejemplo: append a una lista dinámica.

Una lista dinámica (Python list) tiene capacidad fija. Cuando se llena, se duplica. La copia es $O(n)$, pero pasa rara vez.

Si hacés $n$ appends:

• $n$ operaciones, suma total de copias: $1 + 2 + 4 + 8 + \ldots + n \approx 2n$.
• Promedio por append: $O(1)$ amortizado.

Por eso list.append() se considera $O(1)$ aunque a veces tarde más.

📐 Fundamento

Big-O se aplica a tiempo (operaciones) y espacio (memoria) por igual.

def duplicar(lista):           # tiempo O(n), espacio O(n)
    return [x * 2 for x in lista]

def duplicar_inplace(lista):   # tiempo O(n), espacio O(1)
    for i in range(len(lista)):
        lista[i] *= 2

Las dos versiones son $O(n)$ en tiempo. Pero la primera crea una copia ($O(n)$ en espacio), la segunda no.

Trade-off típico: memoización gasta $O(n)$ espacio para reducir $O(2^n)$ tiempo a $O(n)$. Vale la pena casi siempre.

Espacio en recursión: la pila ocupa $O(profundidad)$. Una recursión que va a $n$ niveles consume $O(n)$ espacio incluso si su tiempo es $O(\log n)$.

📐 Fundamento

Una función puede tardar distinto según los datos:

def buscar(lista, x):
    for i, e in enumerate(lista):
        if e == x: return i
    return -1

• Mejor caso: $x$ está en posición 0 → $O(1)$.
• Peor caso: $x$ no está → $O(n)$.
• Caso promedio: asumiendo posición uniforme, $O(n/2) = O(n)$.

Convención: cuando decimos "Big-O" sin clarificar, hablamos del peor caso. Es lo más útil para ingeniería: garantiza límite superior.

Excepciones notables:

• Quicksort: peor $O(n^2)$, promedio $O(n \log n)$. Casi siempre se reporta el promedio.
• Tablas hash: peor $O(n)$ (si todo colisiona), promedio $O(1)$. Se reporta el promedio.

Saber distinguir es importante. Un algoritmo con peor caso malo pero promedio bueno puede ser inaceptable para sistemas críticos (donde necesitás garantías).