Turning amortised into worst-case

May 8th, 2009 by Nils Anders Danielsson

Today I raised an open question related to my paper Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures. The paper discusses a library/type system for Okasaki-style analysis of amortised time complexity (in a call-by-need setting). Assume that the library is used to show that a given program has a given amortised time complexity. The question is whether this program can be automatically turned into one with (nearly) the same complexity, but in a worst-case sense.

Leave a Reply