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,
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.