On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender
You can generally make a persistent data structure with the same asymptotic bounds as the ephemeral structure, ...
I would be very careful with the "generally" here. At least, I am not aware that this has been proved to always be possible.
Here's an informal proof: You can use an intmap to emulate pointers, to turn any ephemeral data structure into a persistent one. That adds at most a log-n factor to lookups and updates. For many structures, this is enough to prove asymptotic bounds equivalence. However, the standard 'pointer' model for ephemeral structures makes the assumption that memory size is limited; otherwise you have to add a log(n) factor there anyways, both to hold the large pointer values that get generated and to actually send the bits to the memory bus. Given this assumption you can take log(memory size) as a constant and argue that pointer lookup and update via the map is O(1).
Also, in assertions about "the same asymptotic bounds", in this and a previous post in this thread, a distinction is important between worst-case and amortized costs. Just to complete the picture...
That's true, but I think the more important distinction is the constant attached to the big O; persistent data structures tend to have much worse constant factors and those factors translate to a general 2x-3x slowdown. It's often true that a worse asymptotic cost algorithm is better because the constant factors are much better and the expected N in your program is small enough. -- ryan