# How do I minimize the cost of some algorithm that performs some operation on a list?

I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $$S_i$$'s are lists (I couldn't think of a better way to write the problem precisely). The "hint" is more of a conjecture which I can't prove than a hint.

Let $$S_0 = \{s^0_1, ..., s^0_n\}$$ be a list containing $$n$$ positive integers. Let $$k$$ be the length of $$S_{i - 1}$$, and define $$S_1, ..., S_{n - 1}$$ recursively as follows: choose $$1 \leq r, s \leq k, \quad r \neq s$$, and define $$\begin{equation*} S_i := (S_{i - 1} \setminus (\{s^{i - 1}_r\} \cup \{s^{i - 1}_s\})) \cup \{s^{i - 1}_r + s^{i - 1}_s\} \end{equation*}$$ E. g. \begin{align*} S_0 &= \{2, 3, 5\} \\ S_1 &= \{5, 5\} \\ S_2 &= \{10\} \end{align*} Clearly, $$S_{n - 1}$$ has a single element. Also, define $$W_i := s^{i - 1}_r + s^{i - 1}_s$$. Consider the quantity $$\sum_{i = 1}^{n - 1} W_i$$. In the previous example, this quantity can be $$15$$ or $$18$$. How do you have to choose $$r$$ and $$s$$ in each step so that $$\sum_{i = 1}^{n - 1} W_i$$ is minimal?

(Hint: Pick $$r, s$$ such that $$s^{i - 1}_r = \min_{x \in S} x$$, and $$s^{i - 1}_s = \min_{y \in S \setminus \{x\}} y$$.)

First, let us understand in more simple terms what you are trying to do. You start with a list of $$n$$ integers. Then you are repeating $$n-1$$ times the following operation: take a pair of integers, and replace them with their sum; this costs you the value of the sum. The costs accumulate additively, and your goal is to minimize the total cost.
You can construct a tree from the $$n-1$$ steps, in the following way. You start with $$n$$ isolated nodes. When adding two integers, you join them to a new root which represents their sum. In the end, you will have a binary tree whose leaves are the $$n$$ original integers. You can check that the total cost is $$\sum_i d_i x_i$$, where $$x_i$$ is the $$i$$'th integer and $$d_i$$ is its depth in the tree (number of edges from root to leaf). (A cost of $$x_i$$ is incurred each time that you add an integer in whose product $$x_i$$ was involved.)