Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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)$.
