chap analysis techniques from to or from to the total number of such changes possible is because each change involves an and each can be part of at most two changes because the total number of unsuccessful comparisons required by move-tofront for any given pair of keys is at most twice that required by the optimal static orderingthe total number of unsuccessful comparisons required by move-to-front for all pairs of keys is also at most twice as high because the number of successful comparisons is the same for both methodsthe total number of comparisons required by move-to-front is less than twice the number of comparisons required by the optimal static ordering further reading good introduction to solving recurrence relations appears in applied combinatorics by fred roberts [rob for more advanced treatmentsee concrete mathematics by grahamknuthand patashnik [gkp cormenleisersonand rivest provide good discussion on various methods for performing amortized analysis in introduction to algorithms [clrs for an amortized analysis that the splay tree requires log time to perform series of operations on nodes when nsee "self-adjusting binary search treesby sleator and tarjan [st the proof for theorem comes from "amortized analysis of self-organizing sequential search heuristicsby bentley and mcgeoch [bm exercises use the technique of guessing polynomial and deriving the coefficients to solve the summation = use the technique of guessing polynomial and deriving the coefficients to solve the summation = findand prove correcta closed-form solution for =