I received some feedback from my recent BCL blog post on the prerelease of the immutable collections that my algorithm complexity table left a few important entries out. Here is the table again, with more data filled in (particularly around list indexer lookup and enumeration):

A noteworthy trait to call out here is that where a List<T> can be efficiently enumerated using either a for loop or a foreach loop, ImmutableList<T> does a poor job inside a for loop, due to its O(log n) time for its indexer. It does fine when using foreach however. This is because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.

Another point to call out from the above table is that SortedSet<T> has the same complexity as ImmutableSortedSet<T>, and in fact in perf tests they show up as pretty close. That’s because they both use binary trees. The significant difference of course is that ImmutableSortedSet<T> uses an immutable one. Since ImmutableSortedSet<T> also offers a Builder class that allows mutation, you can have your immutability and performance too. Woot.