patternMinor
Why addition algorithm is not pseudo- polynomial?
Viewed 0 times
whypolynomialadditionalgorithmpseudonot
Problem
There is something I don't understand.
In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we must sum in the worst case from 1 to T.
So I don't understand why the Addition algorithm is not pseudo-polynomial, when we can add great numbers too.
In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we must sum in the worst case from 1 to T.
So I don't understand why the Addition algorithm is not pseudo-polynomial, when we can add great numbers too.
Solution
The reason is that the runtime of addition is proportional to the number of digits, not the value of the numbers, as it is for subset sum. Remember that the number of digits is the size of the input.
Context
StackExchange Computer Science Q#24531, answer score: 8
Revisions (0)
No revisions yet.