Reputation: 1346
True or False:
Any problem that can be solved using dynamic programming has a polynomial time worst case time complexity with respect to its input size.
Are there any DP solutions which are not polynomial?
Thank you.
Upvotes: 1
Views: 902
Reputation: 9
There are many. The above example is one. Another popular example is dynamic programming solution of Traveling Salesman problem which runs in O(n2^n) time. Note that a brute force solution of Traveling Salesman takes O(n!) time, compared to that a dynamic programming solution is better.
Upvotes: 0
Reputation: 17605
There is a dynamic programming algorithm for the Knapsack problem for which the worst-case complexity is O(Wn)
where W
is the capacity of the knapsack and n
is the number of items. Such a runtime bound is termed as pseudo polynomial (as a value which is encoded in the instance occurs) and cannot be considered as polynomial in the input size. So, short answer: false.
Furthermore, the original question is formulated a bit misleading; the runtime complexity refers to a specific algorithm, not the problem itself.
Upvotes: 2