# Complexity for optimized k-sum problem

Following up on these two posts Generalised 3SUM (k-SUM) problem? https://people.csail.mit.edu/virgi/6.s078/lecture9.pdf

The claim is that k-sum in the general case can be solved in $$O(n^{k/2}log(n))$$

For even π: Compute a sorted list π of all sums of π/2 input elements. Check whether π contains both some number π₯ and its negation βπ₯. The algorithm runs in π(ππ/2logπ) time.

Compute a list of all sums of k/2 input elements. $$O(n^{k/2})$$

Sort this list: $$O(n^{k/2}log(n^{k/2})=O(k/2*n^{k/2}log(n))$$

Sandwich with two pointers to find s and -s. We have a valid answer iff the indices of elements that make up s and -s are nonoverlapping. However, because we have to check each instance of -s in order to validate whether the indices are non-overlapping, we end up having a computation that is $$O(n^{k/2})$$. This means that this step is $$O(n^{k/2} * n^{k/2})$$.

Am I misunderstanding an optimization?

• Depending on the definition they are using the indices don't have to be distinct. Aug 31, 2022 at 15:22
• Yes but say we desire distinct indices, which is the case for the general statement of the k-sum problem Aug 31, 2022 at 16:05
• If you are fine with a randomized algorithm then you can randomly partition the input collection into two sets $A$ and $B$ and consider the variant in which you need to choose $k/2$ elements from each set. If there is a solution to the original instance, then there is a probability of at least $\frac{\binom{k}{k/2}}{2^k}$ that this solution is evenly split between $A$ and $B$ (I'm assuming that $k$ is even for simplicity) which, using Stirling's approximations and dropping constants, is roughly $\frac{1}{\sqrt{k}}$. Repeat $\sqrt{k}\log\frac{1}{p}$ times for a failure probability of about $p$. Sep 2, 2022 at 0:08

In case we desire that all indices are distinct one can use balanced BSTs such as an AVL-Tree to check if indices overlap. For each of the $$O(n^{k/2})$$ sums you also store the set of indices (using a balanced BST as Data structure). Now creating all these sets takes $$O(n^{k/2}k/2\log(k/2))$$, because we need to insert $$k/2$$ elements in every set. Now when check if there exists $$-n$$ for any $$n$$ we need to check if their sets overlap. This again takes $$O(k/2\log(k/2))$$ or for every number $$O(n^{k/2}k/2\log(k/2))$$. Thus for constant $$k$$ we still maintain the runtime $$O(n^{k/2}\log(n))$$
• Using a BST means that checking the intersection of two sums will take $O(k/2 log(k/2))$. However, if you store indices in sets, you can accomplish this in $O(k/2)$. The core problem is still that because it takes $O(n^{k/2}k/2)$ to check every number, and there are $O(n^{k/2})$ numbers, your run time becomes $O(n^k*k/2)$ Sep 1, 2022 at 15:39
• @JasonKang I don't understand - finding a $-n$ for given $n$ only takes log-time since we have sorted the numbers? So for every number we do a binary search to find a matching negative number and then check if indice sets overlap. Where does your runtime come from? Sep 4, 2022 at 2:59
• To add to that, just considering $\{0,1,2,...,m\}$ there are $O(m/2)$ ways to get $m$ as a 2-sum. So the duplicates are probably polynomial in $m$ for $k$-sums. I don't know how to resolve this. Sep 6, 2022 at 5:41