Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n.

In this [thread][1] people discuss solving this problem by sorting the list of integers first and then creating the sums. However none of the solutions seems to be faster than $O(n^2 \log n)$, which is the runtime of just creating all sums and then sorting them.

How would you proof that this is the best you can get or is there a better algorithm to solve the problem.

  • 2
    $\begingroup$ Perhaps you could improve the title of your question. $\endgroup$ – Yuval Filmus Oct 15 '16 at 22:26
  • 4
    $\begingroup$ Welcome to CS.SE! Something is wrong with your link to the "thread". Might you like to edit the question accordingly? Also, what do you mean by "list of sums"? Do you mean for every subset, take its sum? Or every prefix? Or every contiguous subsequence? something else? We'd like questions to be self-contained. Thank you! $\endgroup$ – D.W. Oct 16 '16 at 1:06

This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$.

This problem is a special case of $X+Y$ sorting. According to Wikipedia, no algorithm whose complexity is better than $O(n^2\log n)$ is known for this problem. The decision tree complexity, however, is only $O(n^2)$. (That is, there is an algorithm which asks at most $O(n^2)$ decisions and outputs the sorted $X+Y$; deciding which question to ask could be difficult.)

Your version (with $X=Y$) is no easier than the general case. Indeed, suppose that $X,Y$ are integer arrays. Let $Z = \{ 4x+1 : x \in X \} \cup \{ 4y+2 : y \in Y \}$. Given the sorted version of $Z+Z$, it is easy to extract $X+Y$ by taking all elements of the form $4m+3$ and extracting $m$.

The $X+Y$ problem is 3SUM-hard. However, this doesn't shed much light on the problem since 3SUM itself can be solved in $O(n^2)$ (and even faster), while the $X+Y$ problem plainly requires $\Omega(n^2)$.

  • $\begingroup$ "better than O(n² log n)" -- that doesn't make any sense. I guess you mean $\Theta$? $\endgroup$ – Raphael Oct 16 '16 at 18:47
  • $\begingroup$ I meant having an upper bound better than $O(n^2\log n)$. $\endgroup$ – Yuval Filmus Oct 16 '16 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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