We’re given an array of n numbers, A[1 · · · n] and want to add up the n numbers

Question

We’re given an array of n numbers, A[1 · · · n] and want to add up the n numbers. Let’s consider the following divide-and-conquer algorithm: It partitions the array into two subarrays, A[1 · · · n/2] and A[n/2 + 1 · · · n] and recurse on them to compute A[1] + ··· + A[n/2], and A[n/2 + 1] + ··· + A[n]. Then it adds up the two sums and return the value. What is the recurrence for the running time? Solve it.

Explanation / Answer

Algorithm SumArray( A) Start if length(A)==0 return 0 else if length(A)==1 return A[1]; middle := length(A)/ 2 right := length(A)- middle leftSum := SumArray(A, middle) rightSum = SumArray(A + middle, right) return leftSum + rightSum End Analysis:- We can see that it divides the problem into two sub problem and tries to solve them Recursively. So : Let T(N). be the total time Take. Since It divides into Two T(N/2) -->for the left Sum T(N/2) -->for the Right Sum 1 ----> Constant time for base case. So, T(N) =. 2T(N/2) + 1 We can apply Masters Theorem to solve it a = 2, b =2 => Nlog22 = N. [N > 1 , So falls into third case] So T(N) = O(N) Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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