Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
All your questions can be answered by understanding the (formal) definition of "runtime". I suggest you revisit it. – Raphael May 8 '14 at 15:30
up vote 8 down vote accepted

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.

share|cite|improve this answer

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".)

share|cite|improve this answer
Ok, I understand. thankyou – Pedro May 8 '14 at 14:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.