GATE CS 2008 Q44 — Asymptotic Worst Case Time and Space Complexity

The subset-sum problem is a well-known NP-complete problem, which means it is both in $\text{NP}$ and is $\text{NP-hard}$. Thus, statements C and D are true.

The algorithm $Q$ runs in $O(nW)$ time. Let us analyze the complexity based on the input encoding:

• Unary Encoding: The number $W$ is represented by a sequence of $W$ ones, so the input size is proportional to $W$. The running time $O(nW)$ is polynomial with respect to the input size $n + W$. Thus, statement A is true.
• Binary Encoding: The number $W$ is represented using $b = \lceil \log_2(W+1) \rceil$ bits. The input size is proportional to $n + b$. Expressing the running time in terms of the input size gives $O(n \cdot 2^b)$, which is exponential in terms of the binary input size. Thus, $Q$ is a pseudo-polynomial time algorithm and does not run in polynomial time for binary encoding. Statement B is false.