Nice article, although a bit terse. One part that jumped out at me was: > It is possible to implement fully persistent arrays in O(1) space per update, with O(

Nice article, although a bit terse. One part that jumped out at me was: > It is possible to implement fully persistent arrays in O(1) space per update, with O(lglgN) time for access and updates [4]. This is surprising because it would guarantee at most a log(log(n)) slowdown for any immutable data structure (instead of the log(n) bound I was aware of). But then I checked out the paper and it turns out that the complexity is conditional: > Fully persistent array use can also be provided at O(1) amortized cost, provided that the algorithm satisfies a simple requirement as to uniformity of access. For those algorithms which do not access the array uniformly or single-threadedly, array reads or updates take at most O(log n) amortized time, where n is the size of the array By uniformity they mean no index is used more than K times the average use-per-index (for some constant K). A simple example of a data structure breaking that condition is a heap. The top element is accessed every query but the bottom elements, that dominate the average, are accessed once per n queries (not a constant).