World's most popular travel blog for travel bloggers.

Spacial complexity of an $O(2^N)$ time-complexity algorithm

, , No Comments
Problem Detail: 

For the following code sample:

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

I understand that the time complexity is $O(2^N)$. However, what I don't understand is how the space complexity is $O(N)$. The argument I have heard for this is that although we have $O(2^N)$ nodes in the tree total, only $O(N)$ exist at any given time. What does that mean, how is that so? If the recursive calls are going to be made until the base case is reached, then don't we have $O(2^N)$ calls to make instead of $O(N)$?

Asked By : Anonymous Human
Answered By : megas

The number of calls is indeed $O(2^{n})$. However, the memory footprint will be $O(n)$.

I guess the point is to clarify how the memory stack works during a recursion. Perhaps the easiest way is to draw a recursion tree to follow the recursive calls. Lets see how the size of the stack changes during these calls through a very small example.

Lets say you want to compute $f(1)$. Your tree will have only three nodes: the root ($f(1)$), a left child ($f(0)$) and a right child ($f(0)$).

Initially the stack is empty. We invoke the function with argument $n=1$. We store what we need in the stack (e.g., temporary variables of this call). This takes constant space, and for convenience lets say that stack size is now equal to $1$.

Next, we invoke the left child $f(0)$. The stack size becomes 2. But $f(0)$ returns immediately. So the stack size is back to 1.

Next, we invoke the right child $f(0)$. The stack size is now 2. $f(0)$ immediately returns 1. So the stack size is now back to 1.

Back at the root node, $f(1)$ has computed both the left and right child and returns its value. The stack size is now 0.

This was a very small example, but you see the stack size was never $3$ (equal to the size of the recursion tree) because the memory stack grows and shrinks as you traverse the tree. For a larger example, you will see that when you visit a node (i.e. at some point of the recursion), any memory you used for the left subtree has now been cleared. You only need memory for the nodes between the root and the current node. Hence, the maximum size is equal to the depth of the tree which is $O(n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63870

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback