When calculating the sum of array, the cost of adding the value one by one is same with the divide and conquer recursive calculation. Why this time the Divide-And-Conquer does not show its performance benefit over adding one by one?
And why the Divide-And-Conquer is much better than comparing one by one on sorting?
What's the core difference between the two case?
First of all, when calculating the sum of an array, if divide and conquer is used, the runtime recurrence will be as follows.
T(n) = 2 * T(n/2) + 1
Via the Master Theorem, this yields a runtime bound of O(n). Furthermore, while being the same runtime bound as sequential addition, this bound is optimal; the output depends on every number in the input, which cannot be read within a runtime bound smaller than O(n).
That being said, divide-and-conquer does not per se yield a better runtime bound than any other approach; it is merely a design paradigm which describes a certain approach to the problem.
Futhermore, sequential addition can also be interpreted as divide and conquer, especially if it is implemented recusively; the runtime bound would be
T(n) = T(n-1) + 1
which is also O(n).
ntimes. So the challenge is to reduce the number of times you examine an element to something less thann. With the sum of an array, each element is examined once. There's no way to reduce once to anything less than once.