New answers tagged polynomial-time
1
Use binary search to find the smallest factor, divide and repeat.
1
Imagine you have an $\epsilon$-approximation algorithm $A$ which runs in $n^2+2^\frac1\epsilon$ on an instance of size $n$ and another one, $B$ which runs in $n^2+\frac1\epsilon$ (to give you an other example).
(I'm not using big-O notation to make it easier to talk about the polynomial bounds).
Now if you say $1/\epsilon$ is a constant, $2^\frac1\epsilon$...
1
$2^{n-1}-1$
Hint: 1) if you are summing with $k$ numbers $x_1,x_2,.., x_k$ note that once you choose upto $k-1$, last selection is forced on you as the next ascending number to $x_{k-1}$.
2) You are allowed to choose first $k-1$ numbers from n-1 numbers
Top 50 recent answers are included
