How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

Question

I am reading a proof that the Subset Sum decision problem is NP-complete.

I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. Also, for this specific problem the size/length of the input is $(n+1)\log{W}$, with $n$ and $W$ being two integer variables ($n$ is the number of available elements in the set and $W$ is the sum we are seeking).

However I am having some trouble when trying to understand the terminology be linear/polynomial in the input size, specifically with these two lines:

The input length is (n + 1) log W, and the running time of O(nW) is not polynomial in this input length.

and

takes O(n log W) time, linear in the input size.

How can I mathematically prove the above two lines? Or what is the mathematical reasoning behind those two statements?

I don't have this conceptual problem when there is only one variable. For example, let's say I have an algorithm with a complexity of $O(x)$ and an input size of $\log_2{x}$. Then, I can express $x$ in terms of the problem size like this: $O(2^{size})$. Now, I can see that the complexity is exponential in the size (in bits) of the problem.

But I don't know how to do this when there are two or more variables in the complexity function (in this case $W$ and $n$).

Answer 1

Suppose that the function $\ell$ represents the input length of an algorithm, in terms of several parameters $\vec{x}$, and suppose that the function $T$ represents its running time, in terms of the same parameters $\vec{x}$. Furthermore, there is a collection of valid parameter settings.

We say that $T$ is linear in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C \ell(\vec{x})$.

Similarly, we say that $T$ is polynomial in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C\ell(\vec{x})^C$.

(We get these definitions from the usual definitions of time complexity.)

In your case, $\ell$ and $T$ depend on two parameters $n,W$, and $\ell(n,W) = (n+1)\log W$. A parameter setting is valid if $n \geq 1$ and $W \geq 2$ (this unstated assumption is needed to guarantee that your running times are positive). You are interested in two functions $T$: $T_1(n,W) = nW$ and $T_2(n,W) = n\log W$.

Let us start with the second function $T_2$. For any valid $n,W$ we have $n+1 \leq 2n$ and so $\ell(n,W) \leq 2T_2(n,W)$. Therefore $T_2$ is linear in $\ell$, with $M = 1$ and $C = 2$.

Now let us consider the first function $T_1$. Suppose that $T_1$ were polynomial in $\ell$, with parameters $M,C$. Thus if $n \geq 1$, $W \geq 2$, and $(n+1)\log W \geq M$, then $nW \leq C[(n+1)\log W]^C$. In particular, taking $n=1$, we get that for any $W \geq 2$, $W \leq C2^C(\log W)^C$. Equivalently, $W = O(\log^C W)$. However, this is clearly false. Therefore $T_1$ is not polynomial in $\ell$.