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

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

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$$.