CODEWITHSUNDEEP
algorithm
Wen Xi
Wen Xi

Reputation: 11

Why Divide-And-Conquer does not show its performance advantage on sum of array?

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?

Upvotes: 0

Views: 189

Answers (1)

Codor
Codor

Reputation: 17605

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).

Upvotes: 6

Related Questions