Change-Making Problem: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
Line 29: Line 29:


[[File:Change-Making Problem - Time.png|1000px]]
[[File:Change-Making Problem - Time.png|1000px]]
== Space Complexity Graph ==
[[File:Change-Making Problem - Space.png|1000px]]
== Time-Space Tradeoff ==
[[File:Change-Making Problem - Pareto Frontier.png|1000px]]

Latest revision as of 09:12, 28 April 2023

Description

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$.

Parameters

$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

Error creating thumbnail: Unable to save thumbnail to destination