Timeline for Complexity for optimized k-sum problem

5 events

when toggle format	what		by	license	comment
Sep 6, 2022 at 5:41	comment	added	plshelp		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 5, 2022 at 3:39	comment	added	Jason		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
Sep 4, 2022 at 2:59	comment	added	plshelp		@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 1, 2022 at 15:39	comment	added	Jason		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 13:47	history	answered	plshelp	CC BY-SA 4.0