current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.5 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 7 down vote favorite 
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.

share|improve this question
2  
Write the formula and solve it. Memory(n) = 1 + max(Memory(n-1), Memory(n-1)) – Raymond Chen 4 hours ago
    
This question is a better fit for cs.stackexchange.com – Nayuki 4 hours ago
up vote 11 down vote accepted

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.

share|improve this answer
1  
But how do you know that this is how the operating system implements recursion? potentially it can execute each call with threads, each one waits for other two... I just don't understand why in the worst case it can be more than O(n). As I see it in the general case it can be O(n) – chris 3 hours ago
5  
Complexity calculations are theoretical, not based on a specific implementation, and this conceptually only needs a single thread, with sequential recursive calls. If you rewrite the code using actual threads, then the complexity will be different. – Barmar 3 hours ago
    
but this is my point. since it's not based on specific implementation you have to consider the worst case scenario. isn't it? – chris 3 hours ago
1  
Not necessarily, you only have to consider what's necessary, not some arbitrarily bad way of implementing it. There are also some simplifying assumptions, such as all numbers taking the same amount of space (if you use Peano numbers, each number takes O(n) space). – Barmar 3 hours ago
    
@chris the OS is not involved anyway, it can't be sneaky and implement calls with threads because it has no say over how you implement calls - and it's you doing it, you're just using a compiler to do it for you here, but you could have written the machine code by hand. If you change the hypothetical situation to "the compiler might decide to waste arbitrary amounts of space", then you have created a hypothetical world about which nothing interesting can be said, so it's not useful. – harold 3 hours ago
up vote 5 down vote

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.

share|improve this answer
up vote 3 down vote

Draw the exponential time complexity tree and the length of any leaf from the tree will be linear. This is the space complexity of the algorithm. Because at any point in the recursive call, any such path will be the calls stored in the stack. 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).

share|improve this answer
    
Why do you have different values in the left and right subtrees? They're both called with n-1 as the parameter. Maybe you thought he was calculating Fibonacci? – Barmar 3 hours ago
    
Sorry, I misread it. I thought it was Fibonacci code. I have corrected it now. – Shubham 3 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.