¿Si la complejidad temporal es cuadrática, la espacial también lo es?

PREGUNTA:

En este caso de complejidad espacial, el tiempo esta como cuadrática, eso es debido a que la colección vendría a ser lineal también? tanto la colección como el bucle for general la notación cuadrática?

RESPUESTA:

Para entender esto bien, tenemos que entender la complejidad espacial (memoria) y cómo interactúa con la complejidad temporal (tiempo de ejecución).

Cuando tienes O(N²) temporal, normalmente es porque hay dos dimensiones de crecimiento en tiempo de ejecución (ejemplo: dos bucles anidados).

Cuando tienes O(n²) espacial, suele ser porque se está almacenando una estructura que crece de manera cuadrática con respecto a los datos de entrada.

¿La colección por sí sola hace que sea cuadrática?

Si creas una estructura de datos que almacena algo de forma cuadrática, entonces sí, podrías tener O(n²) de espacio.

Ejemplo:

matrix = [[0] n for _ in range(n)] # Matriz n x n → O(n²) de espacio*

Aquí, sin importar si usamos bucles o no, ya estamos usando O(N²) de espacio porque tenemos N² elementos en memoria.

¿El bucle for hace que el tiempo sea cuadrático?

Si hay un doble bucle, el tiempo normalmente será O(n²), porque cada iteración del primer for hace que el segundo for se ejecute n veces.

Ejemplo:

for i in range(n):

for j in range(n):

print(i, j) # Esto se ejecuta n n veces → O(n²) de tiempo*

Aquí el espacio sigue siendo O(1) porque no estamos guardando nada extra, solo estamos imprimiendo valores.

Pero si dentro del bucle creamos una estructura de datos que crece con cada iteración, podríamos generar O(N²) de espacio también