sir,answer of B should be O(1).Here we are storing values of function foo when it is computed once.So all time only maximum 3 activation records present in the recursion stack.ex,suppose foo(4) is called from main.So,foo(4) will be pushed in the stack.then foo(0),which will be returned.So.present content of the stack is foo(4).Now foo(1) will be pushed,which will push foo(0).So,present content is foo(4)foo(1)foo(0),ie 3 activation records.Now,foo(0),foo(1) will be popped one by one.Now there is foo(4).Then foo(2) will be pushed,which will then push(0) and it will be returned immediately,then foo(1) and it will also be returned,because it's value is already stored.So conten of the stack was foo(4)foo(2)foo(0) and after that foo(4)foo(2)foo(1).Now,foo(2) will be returned.Now,foo(3) will be called,ie.foo(3)will be pushed,which will push foo(0),returned,then foo(1),will be returned,then foo(2)and it will be returned,as value of it is already stored.So here stack contents would be foo(4)foo(3)foo(0) then foo(4)foo(3)foo(1) then foo(4)foo(3)foo(2).So,any value of n,always maximum 3 activation records present in the stack.So,here space complexity should be O(1).