What is the time complexity of binary sum (recursion) [duplicate]

Question

This question already has answers here:

Is there a system behind the magic of algorithm analysis? (3 answers)

Closed 8 years ago.

Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.

There is an example of algorithm which uses a recursion to calculate sum of all elements of the array:

public static int binarySum(int[ ] data, int low, int high) { 
 if (low > high) // zero elements in subarray
 return 0;
 else if (low == high) // one element in subarray
 return data[low];
 else {
 int mid = (low + high) / 2;
 return binarySum(data, low, mid) + binarySum(data, mid+1, high);
 }
}

It further says:

the running time of binarySum is O(n), as there are 2n−1 method calls, each requiring constant time.

I don't understand why it is that the time complexity is O(n) and not O(logn). What am I missing here?

Answer 1

First of all, calculating the sum can't be better than $O(n)$ in the general case because you have to inspect all elements in order to determine the sum.

The function also does not halve the problem size every step: instead of choosing one subarray, as in binary search, we sum both subarrays. This does not save work at all.

We can determine the running time using the recurrence relation:

$$T(0) = T(1) = 1$$ $$T(n) = 2 \times T(n/2) + 1$$

Setting $k = log_2(n)$ we can write this this as:

$$T'(0) = 1$$ $$T'(k) = 2 \times T'(k-1) + 1$$

Now we can use:

$$T'(n) = \sum_{i = 1}^{k} 2^i \times 1$$ $$= 2^{k + 1} - 1 = 2 \times 2^{k} - 1$$ $$= 2 \times n - 1$$