Analyze the running time of Algorithm BinarySum (Code Fragment 3.41) for arbitrary values of the input parameter n.

Code Fragment 3.41: Summing the elements in an array using binary recursion.

When an algorithm makes two recursive calls, we say that it uses binary recursion. These calls can, for example, be used to solve two similar halves of some problem, as we did in Section 3.5 for drawing an English ruler. As another application of binary recursion, let us revisit the problem of summing the n elements of an integer array A. In this case, we can sum the elements in A by: (i) recursively summing the elements in the first half of A; (ii) recursively summing the elements in the second half of A; and (iii) adding these two values together. We give the details in the algorithm of Code Fragment 3.41, which we initially call as BinarySum(A,0,n).

Algorithm BinarySum(A, i,n):

Input: An array A and integers i and n

Output: The sum of the n integers in Astarting at index i

ifn= 1 then

returnA[i]

returnBinarySum(A, i,⌈n/2⌉) + BinarySum(A, i+⌈n/2⌉,⌊n/2⌋)