4 ms·
Time is how long it takes to run, which is based on how many operations you will use. Space is how much memory you need to run it. Frequently in operations th
by btilly 10y ago
Time is how long it takes to run, which is based on how many operations you will use.
Space is how much memory you need to run it.
Frequently in operations there is a tradeoff between time and space. The classic example being that saving previous results in a lookup table requires more space but saves time because you eliminate repeat calculations.
We already had O(2^n) time with O(n) space, or O(2^(n/2)) time with O(2^(n/4)) space. This algorithm represents a new tradeoff between those two points.
Note that these are all worst case scenarios. In practice for sets of modest sized integers, subset sum is solvable in reasonable time and space. See https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... for details.