# Space complexity analysis of binary recursive sum algorithm

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:

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?

• 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. Aug 14 '14 at 22:06
• HEKTO is right. Perhaps when you learn about call stack and method context frames in call stack, you will see this even clearer. Aug 15 '14 at 4:45
– Maha
Aug 15 '14 at 6:30
• @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? Nov 19 '20 at 20:22
• @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. Nov 20 '20 at 16:36

• 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.
• 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,
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).