# Why addition algorithm is not pseudo- polynomial?

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.

• All your questions can be answered by understanding the (formal) definition of "runtime". I suggest you revisit it.
– Raphael
May 8, 2014 at 15:30

The subset sum algorithm runs in time $\tilde{O}(S)$, where $S$ is the sum we're looking for. The input length is $n = \log S$, since it takes this many bits to encode $S$ in binary. Overall, the algorithm takes time $\tilde{O}(2^n)$, which is exponential.
In contrast, you can add two $n$-bit numbers in $\tilde{O}(n)$, which is polynomial time.
(The notation $\tilde{O}(f(n))$ usually means "up to logarithmic factors", but here I use it to mean "roughly".)