What is the Space Complexity of this given code snippet?

Question

The time complexity is O(2^N). How to derive the space complexity for this code?

int f(int n){ 
   if(n <= 1){
      return 1;    
   }
   return f(n-1) + f(n-1);
}

Answer 1

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

quick reference

Basically code snippet is a recursive code for input n it recursively call for n-1

calling example for value 3:

f(3) f(2) + f(2) f(1) + f(1) [for one f(2) , like wise other two]

the order of execution will be like DFS traversal.

Due recursion the program will reuse the same program space which used before.

max depth of the tree will results in the space complexity

O(N) - where N is the input number

for recursions to work program uses Stack Memory