similar argument was used in our analysis for the partition function in the quicksort algorithm (section while on any given pass through the while loop the left or right pointers might move all the way through the remainder of the partitiondoing so would reduce the number of times that the while loop can be further executed our final example uses amortized analysis to prove relationship between the cost of the move-to-front self-organizing list heuristic from section and the cost for the optimal static ordering of the list recall thatfor series of search operationsthe minimum cost for static list results when the list is sorted by frequency of access to its records this is the optimal ordering for the records if we never allow the positions of records to changebecause the most frequently accessed record is first (and thus has least cost)followed by the next most frequently accessed recordand so on theorem the total number of comparisons required by any series of or more searches on self-organizing list of length using the move-to-front heuristic is never more than twice the total number of comparisons required when series is applied to the list stored in its optimal static order proofeach comparison of the search key with record in the list is either successful or unsuccessful for searchesthere must be exactly successful comparisons for both the self-organizing list and the static list the total number of unsuccessful comparisons in the self-organizing list is the sumover all pairs of distinct keysof the number of unsuccessful comparisons made between that pair consider particular pair of keys and for any sequence of searches sthe total number of (unsuccessfulcomparisons between and is identical to the number of comparisons between and required for the subsequence of made up only of searches for or call this subsequence sab in other wordsincluding searches for other keys does not affect the relative position of and and so does not affect the relative contribution to the total cost of the unsuccessful comparisons between and the number of unsuccessful comparisons between and made by the moveto-front heuristic on subsequence sab is at most twice the number of unsuccessful comparisons between and required when sab is applied to the optimal static ordering for the list to see thisassume that sab contains as and bswith < under the optimal static orderingi unsuccessful comparisons are required because must appear before in the list (because its access frequency is highermove-tofront will yield an unsuccessful comparison whenever the request sequence changes