0
$\begingroup$

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

However, I don't follow this claim. The quote reads

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Depending on the definition they are using the indices don't have to be distinct. $\endgroup$
    – plshelp
    Commented Aug 31, 2022 at 15:22
  • $\begingroup$ Yes but say we desire distinct indices, which is the case for the general statement of the k-sum problem $\endgroup$
    – Jason
    Commented Aug 31, 2022 at 16:05
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Commented Sep 2, 2022 at 0:08

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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)$ $\endgroup$
    – Jason
    Commented Sep 1, 2022 at 15:39
  • $\begingroup$ @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? $\endgroup$
    – plshelp
    Commented Sep 4, 2022 at 2:59
  • $\begingroup$ There can be multiple numbers of the same sum. Given the numbers [1234] the array of k/2 (in this case 2) sums includes 5 twice (once from 1,4 and 2,3). Although you can bound the number of duplicates that occur from k/2 sums, it will likely be on the order of O(k). Checking each duplicate is expensive in k $\endgroup$
    – Jason
    Commented Sep 5, 2022 at 3:39
  • $\begingroup$ 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. $\endgroup$
    – plshelp
    Commented Sep 6, 2022 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.