Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top