Extracting 2 numbers n times and placing back the addition in O(n) instead of O(n*log(n))

This is not a full answer. But if the list was sorted, then your problem is easiy doable in O(n). To do it, arrange all of the numbers in a linked list. Maintain a pointer to a head, and somewhere in the middle. At each step, take the top two elements off of the head, print them, advance the middle pointer until it is where the sum should go, and insert the sum.

The starting pointer will move close to 2n times and the middle pointer will move about n times, with n inserts. All of those operations are O(1) so the sum total is O(n).

In general you cannot sort in time O(n), but there are a number of special cases in which you can. So in some cases it is doable.

The general case is, of course, not solvable in time O(n). Why not? Because given your output, in time O(n) you can run through the output of the program, build up the list of pairwise sums in order as you go, and filter them out of the output. What is left is the elements of the original list in sorted order. This would give a O(n) general sorting algorithm.

Update: I was asked to show how could you go from the output (10, 11), (12, 13), (14, 15), (21, 25), (29, 46) to the input list? The trick is that you always keep everything in order then you know how to look. With positive integers, the next upcoming sum to use will always be at the start of that list.

Step 0: Start  input_list: (empty)  upcoming sums: (empty)Step 1: Grab output (10, 11)  input_list: 10, 11  upcoming_sums: 21Step 2: Grab output (12, 13)  input_list: 10, 11, 12, 13  upcoming_sums: 21, 25Step 3: Grab output (14, 15)  input_list: 10, 11, 12, 13, 14, 15  upcoming_sums: 21, 25, 29Step 4: Grab output (21, 25)  input_list: 10, 11, 12, 13, 14, 15  upcoming_sum: 29, 46Step 5: Grab output (29, 46)  input_list: 10, 11, 12, 13, 14, 15  upcoming_sum: 75

This isn't possible in the general case.

Your problem statement reads that you must reduce your array to a single element, performing a total of n-1 reduction operations. Therefore, the number of reduction operations performed is on the order of O(n). To achieve a overall running time of O(n), each reduction operation must run in O(1).

You have clearly defined your reduction operation:

• remove the 2 minimal elements in the array and print them, then
• insert the sum of those elements into the array.

If your data structure were a sorted list, it is trivial to remove two minimal elements in O(1) time (pop them off the end of the list). However, reinserting an element in O(1) is not possible (in the general case). As SteveJessop pointed out, if you could insert into a sorted list in O(1) time, the resultant operations would constitute an O(n) sorting algorithm. But there is no such known algorithm.

There are some exceptions here. If your numbers are integers, you may be able to use "radix insert" to achieve O(1) inserts. If your array of numbers are sufficiently sparse in the number line, you may be able to deduce insert points in O(1). There are numerous other exceptions, but they are all exceptions.

This answer doesn't answer your question, per se, but I believe it's relevant enough to warrant an answer.

If the range of values is less than n, then this can be solved in O(n).

1> Create an array mk of size equal to range of values and initialize it to all zero

2> traverse through the array and increment value of mk at the position of the array element. i.e if the array element is a[i] then increment mk[a[i]]

3) For presenting the answers after each of the n-1 operations follow the following steps:

There are two cases:

Case 1 : all of a[i] are positive

        traverse through mk array from 0 to its size        cnt = 0        do this till cnt doesn't equal 2          grab a nonzero element decrease its value by 1 and increment cnt by 1        you can get two minimum values in this way        present them         now do mk[sum of two minimum]++

Case 2 : some of a[i] is negative

        <still to update>