De-amortization of Algorithms

TitleDe-amortization of Algorithms
Publication TypeBook Chapters
Year of Publication1998
AuthorsS. Kosaraju R, Pop M.
EditorHsu W-L, Kao M-Y
Book TitleComputing and CombinatoricsComputing and Combinatorics
Series TitleLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-64824-6

De-amortization aims to convert algorithms with excellent overall speed, f ( n ) for performing n operations, into algorithms that take no more than O ( f ( n )/ n ) steps for each operation. The paper reviews several existing techniques for de-amortization of algorithms.