# Tag Info

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