Efficiently get sorted sums of a sorted list

Asked 2008-08-03T21:08:54.977

You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list. Duplicates in the resulting list are irrelevant, you can remove them or avoid them if you like.

To be clear, I'm interested in the algorithm. Feel free to post code in any language and paradigm that you like.

algorithm language-agnostic

Edit Report

1 Answer

No matter what you do, without additional constraints on the input values, you cannot do better than O(n^2), simply because you have to iterate through all pairs of numbers. The iteration will dominate sorting (which you can do in O(n log n) or faster).

answered 2008-09-18T22:15:18.577

Efficiently get sorted sums of a sorted list

1 Answer

Your Answer