3 ms·
> BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data s
by thaumasiotes 7y ago
> BTW, the logarithmic time factor to update a leaf is why you will often see logarithmic factors in time complexities of various operations on immutable data structures.
A mutable tree requires the same logarithmic time factor to update a leaf, because it also requires logarithmic time to access the leaf. It seems like the real difference between the mutable and the immutable structure is that the mutable structure requires O(1) space to do the update, while the immutable one requires O(log n) space in addition to the common requirement of O(log n) time.
- dwohnitmok 7y agoSort of. Structural sharing generally actually results in amortized constant space operations if you don't need the copies. In this case, if you aren't actually using the other tree, the nodes could be GC-ed. In the most ideal case they could be GC-ed as you're constructing the new nodes, though I imagine this essentially never happens (hence amortized). But regardless you're right that the thing to focus on is space rather than time when looking at how it would be different in an immutable vs mutable context. Also my comment was incomplete. What I should've added is that most immutable data structures are trees under the hood in some form or another, hence many operations have a logarithmic factor. Mutable data structures provide more options when you want constant time access.