Theorem 2 shows that the total cost of the Move-to-Front (MF) heuristic is at most twice the cost of the best off-line strategy (over any sequence s of m dictionary operations on an initially empty list). Show this ratio bound is tight in the worst case. That is, for any sufficiently large m, give an adversarial sequence s of m dictionary operations on an initially empty list such that if algorithm A is the optimal off-line strategy for sequence s, then the asymptotic cost ratio is CMF(s)/CA(S) = 2 - 0(1) (i.e., the ratio approaches 2). MF is 2-Competitive THEOREM 2: CMF(s) / 2CA(s) - m, for all A and s. Proof of CLAIM Cont'd: A's List: x1 x2 1 * xit1 k-1-p MF's List: HHH k Accounting for exchanges made by A: Paid exchage by A: MF = CMF + DF (0 + 1 = 1. Free exchage by A: MF = CMF + DF = 0 - 1 = -1