2003-02-27 22:05

Deamortization

About

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. Typically, the worst-case bound should match the amortized bound, although it is known that this is not possible for some problems. It is also highly desirable if the deamortization process is systematic (guided by well-specified principles) or even automatic (done by a compiler); ad-hoc deamortization only makes our already fragmented knowledge even more so.

I would write more about this later.

Examples

Binary Counter

In-order Walk

Lower Bounds


Valid XHTML 1.1! Valid CSS! Maverick Woo