Access Restriction

Author McGeoch, Catherine C. ♦ Bentley, Jon L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.
Description Affiliation: Carnegie-Mellon Univ., Pittsburgh, PA (McGeoch, Catherine C.) || AT&T Bell Laboratories, Murray Hill, NJ (Bentley, Jon L.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 28
Issue Number 4
Page Count 8
Starting Page 404
Ending Page 411

Open content in new tab

   Open content in new tab
Source: ACM Digital Library