The theorem (Bentley & McGeoch, 1985)

  • Assumptions: no insertions, and the items start sorted by time of first access (26:25).

  • Statement: for all access sequences S,

    cost_MTF(S) ≤ 2 · cost_FC(S) (FC = frequency count) (27:04)

  • So move-to-front is never much worse than frequency count (27:29).

Their experiments

  • Frequency count did well; move-to-front usually did just as well and sometimes better; transpose performed badly (27:29).

Connection to splay trees' static optimality

  • Splay trees' static optimality says splay does as well on any access sequence as any fixed tree that never rotates (28:01).
  • The list analogue: if no movement is allowed after an access, the best fixed arrangement is exactly frequency order — so frequency count minimizes total service time for the whole sequence (28:18).
  • Hence Bentley–McGeoch reads as "static optimality for move-to-front" (up to the factor 2) (28:52).

Open point raised in class

  • A student notes the two readings of "frequency count": sorted by final frequency (fixed) vs. re-sorted as frequencies change (dynamic) (29:24, 29:53).
  • Here it means the dynamic version, which makes the theorem stronger than plain static optimality; whether the dynamic version always beats the static one was left unresolved in class (29:53, 30:27).
  • Either way the lecture goes on to prove something strictly stronger than static optimality (30:27).