given set of $n$ positive integers and a target number $T$ there is an dynamic programming algorithm that run in $O(n T)$ time complexity that solves the sub-set sum problem, It is regarded as exponential in terms of $T$, when $T$ is a big number, for the sake of this question assume that there is an algorithm that solves sub-set sum in $O(n \ln {T})$ time complexity, does the algorithm still runs in exponential time and why ? or does it runs in polynomial time(that will put sub-set sum in P) and why ?

I am leaning toward the polynomial time algorithm since you need $O(\ln {T})$ time at least for writing $T$ digits in the memory !! I might be very wrong !!

Thanks in Advance.


1 Answer 1


The standard algorithm with time $O(nT)$ isn't exponential in terms of $T$, it's exponential in terms of input length, as instance with input $T$ (and $n$ numbers $\leq T$ each) has length $O(n\log T)$.

The theoretical algorithm with complexity $O(n \log T)$ would run in polynomial time of input size.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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