(a) 3-Way Max Subarray Sum: In Lecture 2 we saw Divide-and-Conquer algorithm for

Question

(a) 3-Way Max Subarray Sum: In Lecture 2 we saw Divide-and-Conquer algorithm for the Max Subarray Sum problem based on the insight that, for an input array A of length n, the best (consecutive) subarray will either: » lie within A's first half, o lie within A's second half, or » use at least one element from each half Recall that we have an O(n) strategy for the last case: scan forwards to find the largest subarray beginning in the middle, and scan backward to find the largest subarray end- ing in the middle. Derek Amayn thinks that splitting A into three pieces instead of two will speed things up! Derek's modified Divide-and-Conquer algorithm observes correctly that the best subarray will either: » lie within the first two-thirds of A » lie within the last two-thirds of A, or » use at least one element from each third. You may assume n is a power of 3, for simplicity. i. [5 points] Write a recurrence for the amount of work Derek's strategy will take. ii. [5 points] Solve the recurrence using the Master Theorem. Is it O(n log n)?

Explanation / Answer

1.Here problem get divided into 3 subproblem each of size 2n/3,n/3 and as in 3rd case use at least one element from each node which is as you have retrieve through whole array hence c(n)

T(n)=T(2n/3)+T(n/3)+cn;

n to the power log2 with base 3 is less than cn

Now from master

T(n) O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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