3 ms·
Sequential access is O(1) just like mutable arrays. These structures really are fast and practical. The benefits of immutability are enormous. That's why they a
by lenticular 7y ago
Sequential access is O(1) just like mutable arrays. These structures really are fast and practical. The benefits of immutability are enormous. That's why they are so popular.
Edit: That's true about log32 and log2 become close in the limit, but that's irrelevant for practical data sizes. For example,
log2(10^6) ~ 20,
log32(10^6) ~ 4
That's a 5x difference.
- seanmcdirmid 7y agoSequential access in an array has caching advantages because the memory is contiguous. For a linked structure, that is often not true. Linked structure mostly suck at sequential accesses. Extreme random access can actually work against arrays for the same reason. There is a good reason why the subscript of log is often not even mentioned. Logarithmic is logarithmic, no longer what subscript you bother in investing extra space for.
- ericpauley 7y agolog32n/log2n is always 5, highlighting why this is such a meaningless comparison. O(logn) (basically) refers to a constant multiple clogn, by which logic O(log32n) = O(5log2n) = O(log2n) = O(logn). It's all the same. Case in point, if your algorithm takes log32n operations but each OP takes 5x longer its exactly the same as log2n. This is true for any value n, not just large values.
- seanmcdirmid 7y agoAh! My explanation was wrong in that sense, thanks for the correction.
- lenticular 7y agoWhoops, brain fart.