Amortized efficiency of list update and paging rules

Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

1485 Scopus citations

Abstract

In this article we study the amortized efficiency of the “move-to-front” and similar rules for dynamically maintaining a linear list. Under the assumption that accessing the ith element from the front of the list takes θ(i) time, we show that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules. Other natural heuristics, such as the transpose and frequency count rules, do not share this property. We generalize our results to show that move-to-front is within a constant factor of optimum as long as the access cost is a convex function. We also study paging, a setting in which the access cost is not convex. The paging rule corresponding to move-to-front is the “least recently used” (LRU) replacement rule. We analyze the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory. No on-line paging algorithm has better amortized performance.

Original languageEnglish (US)
Pages (from-to)202-208
Number of pages7
JournalCommunications of the ACM
Volume28
Issue number2
DOIs
StatePublished - Feb 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Amortized efficiency of list update and paging rules'. Together they form a unique fingerprint.

Cite this