|
| Homework 21Details| Problem
|
|---|
| A
| | 8.5
| | Pick one: 8-10, 8-16c, 8-17, 8-25
|
Problem A:
Problem 8-10 suggests giving an algorithm that runs in O(nM) time. Is that a polynomial-time algorithm with respect to the size of the input? Explain. (Hint: The input consists of n integers, so let's use n as the
size of the input. Now you just need to think about what M can be.)
Note: When giving a dynamic programming algorithm, give a recursive formula and specify how the values will be computed to yield an efficient algorithm.
|