[Solved]: Impact on the order of elements on the cost of searching in a linked list

Problem Detail: 

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) $$

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

2. 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.

Asked By : setlio

Answered By : Yuval Filmus

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 < 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} < 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22264

3.2K people like this

 Download Related Notes/Documents