Impact on the order of elements on the cost of searching in a linked list I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there.

Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$.
Assume that the cost of examining a particular element $X_i$ is $C_i$. Note that to examine $X_i$, 
one needs to scan through all elements in front of $X_i$. Let $P_i$ be the probability of 
searching for element $X_i$, so the total cost for all searches is 
$$
\sum_{j=1}^{n} \left( P_j \cdot \sum_{i=1}^{j} C_i \right)
$$


Show that storing elements in non-increasing order of $P_i/C_i$ does not necessarily minimize the total cost. 
Show that storing elements in non-decreasing order of $P_i$ does not necessarily minimize the total cost. 


Any help and direction how to approach the problem will be highly appreciated.
I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P_i/C_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P_i/C_i &lt; P_{i+1}/C_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P_i$, we have to pay $C_{i+1}$ more. When looking for $B$, which happens with probability $P_{i+1}$, we have to pay $C_i$ less. So
$$ \Delta = P_i C_{i+1} - P_{i+1} C_i = (P_i/C_i - P_{i+1}/C_{i+1}) C_i C_{i+1} &lt; 0. $$
In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

How I found this proof: I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible. 

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.