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 algorithmbinarySum()
uses $O(\log n)$ additional space. This is big improvement over $O(n)$ needed by thelinearSum()
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?
binarySum
calls. Each abinarySum
call finishes after all its children finish. So, whenbinarySum
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. $\endgroup$ – HEKTO Aug 14 '14 at 22:06binarySum
calls on the same level of the tree can use the same piece of space. $\endgroup$ – HEKTO Nov 20 '20 at 16:36