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:

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?

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,

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.