Abstract. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has cons

21 (b) p(T )= q(Ti0 )=) p(S )> q(S ) To carry out the induction proof, we will start by demonstrating the hypotheses for an appropriate base case. For the induction step, we assume the ve hypotheses for i+ 1, derive a transformation Oi, and show the validity of the hypotheses for i. Then we de ne T 0= T1, and note that the non-increasing depth property is satis ed for all pi 6= x. We de ne O0= O1, and note all of the inversions between non-referenced elements in T 0 have been accounted for, i.e., I T; T 0]+ jO0 j jOj: Finally, we repeat that because the only transpositions removed from O are between non-referenced elements, the depths, and thus the reference costs, of all referenced elements remains identical between O and O0 .The base case. For the base case, we de ne Ob= O; Tb0= O?1 (T 0). (Notationally, b is N+ 1.) Then (1) and (2) follow from our de nition (Ib is zero). Items (3) and (4) are vacuous. We must show that items (5)(a) and (5)(b) are true for all non-referenced elements in Tb0. For item (5)(a), by construction of S 0, elements q deeper than x in S are una ected by the shift, q(S )> x(S )=) q(S )= q(S 0 ) so q(T )= q(Tb0 ), while elements q closer to the front of S are\shifted down", q(S )< x(S )=) q(S 0 ) 6= q(S ) (indeed q(S 0 )> q(S )), so q(T ) 6= q(Tb0 ). Finally, for (5)(b), p(T )= q(Tb0 ); p 6= q implies p(T ) 6= p(Tb0) implies (by (5)(a)) p(S )< x(S ), similarly q(S )< x(S ). By construction, p(S 0 )> p(S ) by one non-referenced position, but q(S 0 )= p(S ) since O?1 takes q to location p(T ) in Tb0. Hence p(S 0 )> q(S 0 ). Induction step. Now suppose the entire hypothesis is true for i+ 1 (including for example b= N+ 1). We will construct an appropriate mapping Oi that satis es the hypotheses for i. We describe three stages, depending on whether the element x has yet been considered. Denoting by z the location of x in T, so that x= pz, we consider pi for (i) i> z, (ii) i= z, (iii) i< z in turn. Case (i): i> z . We have the non-decreasing depth property for j 2 i+1;:::; N, which because i> z requires strictly that pj (Ti0+1 )= pj (T ) for all locations j . In this case, the non-decreasing depth property applied to i will require strictly that pi (T )= pi (T 0). Throughout this stage, in particular, the non-decreasing depth property for i implies Ii Ti0; T]= 0. We examine the current occupant of position i in Ti0+1 . There are three possibilities to consider:{ The occupant is pi itself, pi(Ti0+1 )= pi(T ). In that case, set Oi= Oi+1 . The non-decreasing depth property is (precisely) satis ed. Hypotheses (1) and (2) follow immediately from their validity for i+ 1; hypothesis (3) and (4) follow from the depth property; and hypothesis (5) is more restrictive, hence va

lid.{ The occupant is x, x(Ti0+1 )= pi (T ). In this case, Ti0 will be obtained by interchanging pi with x. We observe that pi (Ti0+1 )< x(Ti0+1 ) (by the depth property at i+ 1), and x(S 0 )< pi (S 0 ) by construction (x is the front-most non-referenced element in S 0 ), so x and pi are inverted by Oi+1, and there