PUERTA | PUERTA-CS-2005 | Pregunta 82

Considere la siguiente función C:

double foo (int n)
{
    int i;
    double sum;
    if (n = = 0) return 1.0;
    else
    {
        sum = 0.0;
        for (i = 0; i < n; i++)
            sum += foo (i);
        return sum;
    }
}

Supongamos que modificamos la función anterior foo() y almacenamos los valores de foo (i), 0 < = i < n, a medida que se calculan. Con esta modificación, la complejidad del tiempo para la función foo() se reduce significativamente. La complejidad espacial de la función modificada sería:
(A) O(1)
(B) O(n)
(C) O(n!)
(D) O(n ⁿ )

Respuesta: (B)
Explicación: Complejidad espacial ahora es también O(n).

Necesitaríamos una array de tamaño O(n). El espacio necesario para las llamadas recursivas sería O(1), ya que los valores se tomarían de la array almacenada en lugar de realizar llamadas a funciones una y otra vez.
Cuestionario de esta pregunta