0

Given n integers a1,a2..an and some integer S. To test whether there exists xi belongs to {0,1} such that:

                       **S = Summation(xi*ai) [i=0 to n]**

Test whether when using (x1,x2,..xn) := (0,0,..,0) in the above eqn, this would work. Then continue with testing (x1,x2,....,xn) :=,(0,0,0,...1), etc., until finally testing (x1,x2,....xn) := (1,1,.....1). If the above eqn is satisfied for one of these tests, then return True, else False.

1) Analyze the time complexity? 2) Does the algo take polynomial time?

argumentopruvo
  • 13

1 Answers1

1

There are $2^n$ integer of $n$ bits, and computing one sum is a linear-time operation.

  1. Hence for the whole procedure, in the worst case $$O(n2^n).$$

  2. This isn't polynomial.

Indeed, for any degree $d$, you can find a value of $n>2d$ such that

$$n^d<2^n,(n+1)^d<2^{n+1},(n+2)^d<2^{n+2}\cdots,$$

as the ratio

$$\left(\frac{n+1}{n}\right)^d<\left(1+\frac1{2d}\right)^d<e^{1/2}<2.$$