Jay Patel
Jay Patel

Reputation: 1346

Dynamic Programming : Concept

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

Answers (2)

Hasan
Hasan

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

Codor
Codor

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

Related Questions