CODEWITHSUNDEEP
calgorithm
chris
chris

Reputation: 113

What is the space complexity of this code?

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

I know that the time complexity is O(2^n) and I understand why.

But I don't understand why the space complexity is O(n). I was told that it's because at any given time there are only n nodes, but it doesn't make sense to me.

Upvotes: 11

Views: 754

Answers (3)

Shubham
Shubham

Reputation: 2855

Draw the exponential time complexity tree and the length of path of any leaf from the root of the tree will be linear. This linear path is the space complexity of the algorithm. The algorithm will traverse each of those paths to solve the problem but at any point the maximum number of recursive calls stored in the stack will be linear. Ex: for f(3)

         3 
       /   \ 
     2      2 
    / \    / \ 
   1   1  1   1

The maximum length from root to leaf is O(n). Thus, the space complexity is also O(n).

Upvotes: 5

Barmar
Barmar

Reputation: 781068

Because the second f(n-1) can't run until the first one completes (or vice versa -- it's the same either way). The first call will recurse n times, then all those will return, so that will push a total of n stack frames. Then the second call will do the same thing.

So it never gets more than n levels deep in the recursion, and that's the only contributor to space complexity.

Upvotes: 15

Saeed Amiri
Saeed Amiri

Reputation: 22555

Space complexity is O(n) because one side of recursion, reaches the leaves, and returns up, until the root, similar happens for the other side of recursion and in every middle step, the space used in the recursion cannot be bigger than O of depth of recursion tree.

Upvotes: 7

Related Questions