JavaScript Question

In merge sort, which uses a divide-and-conquer approach to sortan array of values. There are many more algorithms that takes suchan approach. Implement a function that computes the sum of an arrayof integers using divide and conquer. The function should have thefollowing signature:

function divideAndConquerSum(a);

where a is the array. The recursive calls sum up the numbers inthe base case, and ?merges? the sums of the recursive callsotherwise. For example, the return value for the array a=[1,5,-1,4] is 9.To make it a bit more interesting, instead ofsplitting into two sub-arrays like in merge sort, I want you tosplit into three sub-arrays at each divide step. Submit yourcomplete code, including a function that demonstrates that yourimplementation works with a few test inputs .Hint: Like in theimplementation of merge sort, you may need a helper function thatdoes the actual recursion.

2 Runtime Analysis (Theory part)

What is the runtime of the algorithm that you implemented?Provide a recurrence relation forT(n) according to this concept formerge sort (you can ignore constant1

factors)

and solve it . Give the final ? complexity . Describe yourreasoning briefly with stepwise.

Transcribed Image Text:

Mergesort Running Time. 1. If the array has 0 or 1 elements, it's sorted. Stop. 2. Split the array into two approximately equal-sized halves. 3. Sort each half recursively (using Mergesort). 4. Merge the sorted halves to produce one sorted result: ▷ Consider the two halves to be queues. T(1) = 1 1 2T (n/2) n ▷ Repeatedly dequeue the smaller of the two front elements (or dequeue the only front element if one queue is empty) and add it to the result. 21 Mergesort Running Time. 1. If the array has 0 or 1 elements, it's sorted. Stop. 2. Split the array into two approximately equal-sized halves. 3. Sort each half recursively (using Mergesort). 4. Merge the sorted halves to produce one sorted result: ▷ Consider the two halves to be queues. T(1) = 1 1 2T (n/2) n ▷ Repeatedly dequeue the smaller of the two front elements (or dequeue the only front element if one queue is empty) and add it to the result. 21

Answer rating: 100% (QA)

Answer Heres the implementation of the divideAndConquerSum function in JavaScript function divideAnd... View the full answer