by Nils Anders Danielsson on May 8, 2009.
Tagged as: Lunches.
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.