1 Divide and Conquer Sum In the lectures, we\'ve covered merge sort, which uses

Question

1 Divide and Conquer Sum In the lectures, we've covered merge sort, which uses a divide-and-conquer ap- proach to sort an array of values. There are many more algorithms that take such an approach. Implement a function that computes the sum of an array of integers using divide and conquer. The function should have the following signature: function divideAndConquerSum (a); where a is the array. The recursive calls sum up the numbers in the base To make it a bit more interesting, instead of splitting into two sub-arrays Submit your complete code, including a function that demonstrates that Hint: Like in the implementation of merge sort, you may need a helper case, and "merge" the sums of the recursive calls otherwise. For example, the return value for the array a [1,5,-1,4] is 9. like in merge sort, I want you to split into three sub-arrays at each divide step. your implementation works with a few test inputs. function that does the actual recursion. Total 5 points.

Explanation / Answer

1. Please find the code below.

CODE

====================

function divideAndConquerSum(a) {
return divideAndConquerSum(a, 0, a.length-1);
}

function divideAndConquerSum(a, low, high) {

if(high == low)
return a[low];

var mid1 = low + (high - low)/3;
var mid2 = mid1 + (high - low)/3;

return divideAndConquerSum(a, low, mid1 - 1) + divideAndConquerSum(a, mid1 + 1, mid2 - 1) + divideAndConquerSum(a, mid2 + 1, high);
}

let a = [1, 5, -1, 4];
console.log(divideAndConquerSum(a));

2. The recurrence relation of this algorithm is given as:

T(n) = 3*T(n/3) + c [where c is a constant]

Using Subsitution method, we get

T(n) = 3*3 T(n/9) + 3*c + c

= 3*3*3*T(n/27) + 9c + 3c + c

= 3i * T(n/3i) + (1)

For i = log3n, we get

T(n) = log3n + (1)

= (log3n) (Answer)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.