La memoria también forma parte del algoritmo

Un algoritmo no deja de ser costoso porque termine rápido. Puede copiar una entrada gigante, llenar una caché sin límite o agotar la pila con recursión. La complejidad espacial pregunta cuánta memoria necesita la solución mientras trabaja, y el pico importa más que lo que queda al final.

Espacio total y espacio auxiliar

Hay dos medidas que conviene separar. El espacio total incluye la entrada; el espacio auxiliar cuenta sólo la memoria extra creada por el algoritmo.

Ordenar un arreglo de $n$ elementos siempre requiere almacenar esos $n$ elementos, pero un algoritmo in place puede usar sólo $O(1)$ espacio auxiliar. Mergesort sobre arreglos suele necesitar además un buffer de $O(n)$. Decir simplemente “usa $O(n)$ memoria” sin aclarar la convención puede hacer parecer iguales dos soluciones distintas.

Lo que importa es el pico

La memoria se analiza en el momento de mayor uso. Si un proceso crea un arreglo de tamaño $n$, lo descarta y después crea otro, el pico puede ser $O(n)$, no $O(2n)$; nunca necesita ambos a la vez. Si conserva los dos, la cuenta exacta cambia pero el orden sigue siendo $O(n)$ porque Big O elimina constantes.

En producción, esas constantes vuelven a importar: dos buffers de 500 MB pueden ser la diferencia entre funcionar y recibir un out of memory, aunque ambos diseños sean lineales.

La pila también es memoria

La pila de llamadas también es memoria auxiliar. Este factorial parece no crear ninguna colección:

const factorial = (value: number): number =>
  value <= 1 ? 1 : value * factorial(value - 1);

Pero antes de volver necesita conservar una llamada por cada valor. La profundidad es $n$, así que usa $O(n)$ espacio de pila. Una versión iterativa mantiene sólo el acumulador y el índice: $O(1)$ auxiliar.

En un árbol balanceado, una recorrida recursiva usa $O(\log n)$ pila; en un árbol degenerado puede llegar a $O(n)$. La forma de los datos también decide la profundidad.

Las copias que nadie escribió

Operaciones cómodas pueden esconder asignaciones. Cortar un arreglo, concatenar cadenas o usar transformaciones encadenadas suele crear colecciones intermedias. Este pipeline es lineal en tiempo y también puede ser lineal en memoria extra:

const activeNames = users
  .filter((user) => user.active)
  .map((user) => user.name);

Eso no lo vuelve incorrecto. La claridad suele valer más que ahorrar una colección pequeña. Pero con millones de elementos conviene saber si el runtime fusiona operaciones o conserva el resultado completo de cada etapa.

Comprar velocidad con memoria

Muchas optimizaciones de tiempo compran velocidad con memoria. Una tabla hash guarda índices extra para buscar en tiempo esperado constante. La memoización conserva resultados para no repetir subproblemas. Una caché evita red y disco a cambio de ocupar RAM.

El intercambio también funciona al revés: comprimir datos, procesar por streaming o recalcular un valor reduce memoria pero agrega CPU. No existe una complejidad “mejor” sin conocer la restricción real del sistema.

Cuando no hace falta cargar todo

Si sólo necesitás una suma, un máximo o una cantidad, muchas veces no hace falta cargar toda la entrada. Un algoritmo de streaming procesa un elemento, actualiza un estado pequeño y lo descarta. Para calcular el promedio alcanza con suma y cantidad: $O(1)$ memoria auxiliar, aunque se lean $n$ valores.

La pregunta útil es: ¿qué información del pasado necesito conservar para procesar el próximo elemento? Si la respuesta cabe en pocos acumuladores, guardar la colección completa puede ser un costo accidental.

Dejar de usar no es liberar

En lenguajes con garbage collector, dejar de usar un objeto no garantiza que la memoria se libere en ese instante. Además, una referencia olvidada puede mantener vivo un grafo entero. La complejidad asintótica supone que entendemos qué objetos siguen alcanzables; el perfilador muestra si esa suposición coincide con el runtime.

Medir memoria no reemplaza el análisis, y el análisis no reemplaza medir. Uno predice cómo crecerá el consumo; el otro encuentra buffers, retenciones y costos del entorno que el modelo no vio.

Dónde se va la memoria de verdad

Cierre

Contá la entrada, la memoria auxiliar, la pila y las copias temporales; después mirá el pico. Una solución rápida que no cabe en memoria no es una solución. El objetivo no siempre es usar menos: es saber qué recurso estás gastando y por qué ese intercambio conviene para la escala real del problema.