Change-Making Problem (Change-Making Problem)

From Algorithm Wiki
Revision as of 09:12, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given an unlimited amount of coins of denominations $c_1, \ldots, c_n$, and a desired sum $S$, find the minimum number of coins necessary to make $S$.


$n$: number of coin denominations

$S$: sum to be made

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Brute Force 1940 $O(S^n)$ $O(n)$ Exact Deterministic
Dynamic Programming 1953 $O(Sn)$ $O(Sn)$ Exact Deterministic Time
Probabilistic Convolution Tree 2014 $O(n \log n)$ $O(n log n)$ Deterministic Time & Space

Time Complexity Graph

Change-Making Problem - Time.png