Algorithms and Data Structures · Middle · Question 44 of 75
What is the complexity of the coin change DP for amount A and k coin types?
- 1O(kᴬ)
- 2O(A + k)
- ✓Correct answer: O(A × k)
Explanation
For each amount from 1 to A you try each of the k coins once. Exponential O(kᴬ) is the brute-force recursion without caching.
Test yourself
Take the Algorithms and Data Structures · Middle quiz: questions and options are shuffled, and you get a review of your mistakes at the end.