hard20 pts · first answer countsdynamic-programmingcomplexitycoin-change

Is O(n × amount) polynomial?

The coin change DP runs in O(n × A), where A is the target amount. Why is it called pseudo-polynomial?

A.A can be exponential in the number of digits that encode itB.It relies on floating point arithmetic for every table cellC.It only works for amounts below 10^6 because of memory limitsD.It is polynomial only when the coins are sorted in advance

Discussion 0

Join free to post in the discussion.

Is O(n × amount) polynomial?

Discussion 0

Related questions