Multiple choice

Consider the following C-function:

The space complexity of the above function is foo O and store the values of foo (i),0 <= i < n, as and when they are computed. With this modification, the time complexity for function fooO is significantly reduced. The space complexity of the modified function would be:

  1. O(1)

  2. O(n)

  3. O(n2)

  4. O(n!)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Here we store values in foo(i ) only when they are completed then in every recursion we require space to store 1 double. So overall n calls we require 0(n)

Keep practicing — related questions