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 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
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?