Consider two items, a and b, for which P(a) = 0.7 and P(b) = 0.3. There are two ways to order these items in the list:

List ab : .

List ba : .

Now consider three items, a, b, and c, for which P(a) = 0.3, P(b) = 0.5, and P(c) = 0.2. There are six ways to order these items:

List	Expected Search Time
abc acb bac bca cab cba	(.3 * 1) + (.5 * 2) + (.2 * 3) = 1.9 (.3 * 1) + (.2 * 2) + (.5 * 3) = 2.2 (.5 * 1) + (.3 * 2) + (.2 * 3) = 1.7 (.5 * 1) + (.2 * 2) + (.3 * 3) = 1.8 (.2 * 1) + (.3 * 2) + (.5 * 3) = 2.3 (.2 * 1) + (.5 * 2) + (.3 * 3) = 2.1

Look at the pattern:

Idea: Order the list by decreasing probability of access!

A list of elements ordered by decreasing probability of access has minimum expected access time.

In list , let element be in the position in the list:

Let's try a proof by contradiction: Assume that has minimum and that there is some pair of adjacent elements that are not ordered by decreasing probability of access:

If we can show that does not have minimum cost, then the assumption is contradicted and

in the minimum-cost list.

The expected access time in is

Create another list, , in which elements and are swapped. Let be the access time in this list.

You might guess that this list has lower expected access time, since , which has higher probability of access, is now closer to the front of the list. Let's see:

If the new list has lower expected access time, then . In other words, .

But our assumption was that . This means that

and the new list does have lower expected access time!

Thus, the assumption is contradicted and we must conclude that, if has minimum expected access time,