Space complexity analysis of binary recursive sum algorithm

Question

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum of all elements of the array:

Algorithm linearSum (arr , n)
 if (n == 1)
 return arr[0] 
 else
 return linearSum (arr , n-1) + arr[n-1]
end linearSum

And the binary sum algorithm which uses binary recursion to calculate sum of all elements of the array:

Algorithm binarySum (arr, i, n)
 if (n == 1)
 return arr[i]
 return binarySum (arr, i, ⌈n/2⌉) + binarySum (arr, i+⌈n/2⌉, ⌊n/2⌋)
end binarySum

It further says:

The value of parameter $n$ is halved at each recursive call binarySum(). Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, is 1ドル + \log_2 n$. Thus the algorithm binarySum() uses $O(\log n)$ additional space. This is big improvement over $O(n)$ needed by the linearSum() algorithm.

I did not understood how the maximum number of method instances that are active at the same time, is 1ドル + \log_2n$.

For example consider the below calls to method with method parameters given in rounded box:

enter image description here

Then in two recursive calls of second row from top, $n = 8$. So, 1ドル + \log_2 8 = 4$. Now I dont get what maximum limit this 4 represent?

• HEKTO: Height of this tree is 4. All the vertices of this tree correspond to binarySum calls. Each a binarySum call finishes after all its children finish. So, when binarySum on the leaves level is active, its parent, grandparent and so on are still active as well. It's called a depth of recursion, which is equal to the height of this tree.
• InformedA: HEKTO is right. Perhaps when you learn about call stack and method context frames in call stack, you will see this even clearer.
• Mahesha999: Ohh great. @hekto please put it in answer
• GilbertS: @HEKTO Yes but how does this mean space complexity is 1 + logn. How are you using less space. The way I see it is that you are basically using the same space but in twos. Like instead of space = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, you have space = (1 + 1) + (1 + 1) + (1 + 1) + (1 + 1). How come space complexity is shown to be 4 instead of 8?
• HEKTO: @GilbertS - the space is reused... If you look at the call tree above (which has a lot of wrongly labeled nodes by the way) you'll notice that all the binarySum calls on the same level of the tree can use the same piece of space.

Answer 1

• In a given tree, all the vertices of this tree correspond to binarySum() calls.
• The value of parameter n to binarySum() is halved at each recursive call.
• Also, each recursive call finishes after all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence.
• Thus when any binarySum() call corresponding to leaves in above call tree is active, its parent, grandparent and so on are still active as well.
• Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, which is always equal to the height of the recursive calls tree is 1 + log$_2$n.
• For example in binarySum() recursive calls tree above, with n = 8, at any of the calls correspnding to leaves,

enter image description here

Why does the depth of recursion affect the space, required by an algorithm? Each recursive function call usually needs to allocate some additional memory (for temporary data) to process its arguments. At least, each such a call has to store some information about its parent call - just to know where to return after finishing. Let's imagine you are performing a task, and you need to perform a sub-task inside this first task - so you need to remember (or write down on a paper) where you stopped in the first task to be able to continue it after you finish the sub-task. And so on, sub-sub-task inside a sub-task... So, a recursive algorithm will require space O(depth of recursion).

@randomA mentioned the Call Stack, which is normally used when a function invokes another function (including itself). The call stack is the part of the computer memory, where a recursive algorithm allocates its temporary data.

• GilbertS: So if you have two recursive functions in binary recursion with the same parent function, does that mean that they will use the same memory to store information about their parent function which is more efficient than if each of them was storing that information in a different location like they would be in linear recursion?