Consider the following C-function: double foo (int n) { int i; double sum; if…
2005
Consider the following C-function:
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 store the values of foo (i), 0 < = 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:
- A.
O(1)
- B.
O(n)
- C.
O(n!)
- D.
O(nn)
Attempted by 59 students.
Show answer & explanation
Correct answer: B
Answer: O(n)
Explanation:
Memoization stores the values of foo(i) for 0 ≤ i < n, so you keep up to n computed values in memory. This requires O(n) space.
The recursion may use a call stack of depth up to n in the worst case, which is an additional O(n) space.
Combining both contributions, the total space complexity remains O(n).