Q81b

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; } } Suppose we modify the above function $foo()$ and stores the value of $foo(i) \ 0 \leq i < n$, as and when they are computed. With this modification the time complexity for function $foo()$ is significantly reduced. The space complexity of the modified function would be: $O(1)$ $O(n)$ $O(n^2)$ $n!$