Complejidad de memoria de variables temporales

[martina-abello]

Si uso una variable temp para poder intercambiar 2 punteros, y esto se hace varias veces en la misma función (dentro de un for o un while), ¿esto le da complejidad espacial O(1) (por ser temporal), mayor a O(1) (por hacerse varias veces, en cuyo caso, puede reducirse con free en cada iteración?), o ni siquiera ocupa espacio adicional (porque hago temp = p1; p1 = p2; p2 = temp;, no se crea un puntero nuevo) ?

[Segismundios]

Hola @martina-abello. En ese caso, la complejidad espacial es O(1), porque lo que importa es el máximo de memoria usada simultáneamente, no la suma de lo que se usa en cada iteración.
Si usaras malloc o calloc sin hacer free de inmediato, entonces sí irías acumulando memoria, ya que estarías reservando más en cada iteración.
Pero si solo usas una variable temporal dentro de un bloque o función, esa memoria se libera automáticamente al salir del scope, así que no afecta la complejidad espacial de forma acumulativa.

[tremendapithon]

Pero puedo usar una variable auxiliar pidiendo calloc, tipo un mini array y lo voy liberando?

[Segismundios]

Claro, igual puedes hacer eso si se va liberando altiro, aunque si es un array, ahí tienes que ver de qué depende el tamaño del array, porque eso va a tener implicancias en la complejidad.

[tremendapithon]

Es un array auxiliar para ordenar, despues sera liberado, la verdad no impacta en la complejidad.