News for hackers. Stuff that matters.
Re:Purely Functional Data Structure by Chris Okasaki [pdf] by okennedy on Tuesday May 30, 2023 @09:34AM (#36124703)
This is the canonical guide to reasoning about amortized runtimes. The exponentially growing ArrayBuffer (O(1) amortized append) is the classical data structure used to teach amortized runtimes, but the O(1) amortized functional queue Okasaki presents here gives a much better intuition for what amortized runtimes are all about.

There are no comments on this comment yet.