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