The dynamic programming algorithm itself for segmented least squares (i.e., not the computation of the least-squares errors) runs in O (na) time. Which of these best describes the reason why? a. There are a linear number of subproblems to solve, each of which takes linear time to solve. b. There are a constant number of subproblems to solve, each of which takes quadratic time to solve. c. There are a linear number of subproblems, each of which takes constant time to solve, and each of which is resolved a linear number of times. d. There are a quadratic number of subproblems to solve, each of which takes constant time to solve.
