Problem 2:

Let [1: ] be a real array. A prefix of X is a subarray [1: ] where 1 , and a suffix of X is a subarray [: ]. The minimum-prefix-product problem is the problem of taking [1:] as input and returning the k such that [1] [2] [] is the smallest possible. The minimum-suffix-product problem is to find k such that [] [ + 1] [] is the smallest possible. The minimum-subarray-product problem is the problem of taking [1: ] as input and returning two integers k and r, (1 ), such that [] [ + 1] [] is the smallest possible.

a. Write a divide-and-conquer algorithm for solving the minimum-prefix-product problem, and another divide-and-conquer algorithm for solving the minimum-suffix-product problem.

b. Write a divide-and-conquer algorithm for solving the minimum-subarray-product problem.

c. Analyze the time complexity of your algorithms