Some time ago I covered in this blog the complexity of Scala immutable collections, explaining a little what happened under-the-hood. Now it's a good moment to back to this topic and apply it for mutable collections.
Using the right tool at the right time is important in every domain. It's particularly useful in the case of collections that can have different complexity for writing and reading. And very often this difference can dictate the use of one specific implementation.
The basic Big O measures (O(1), O(n), O(log n)) are understandable quite easily. However they're not the single ones - especially because of Scala collections. Two variations of them, a little bit less unequivocal, exist - amortized and effective constant time.
