Asymptotic complexity of .NET collection classes

Question

Are there any resources about the asymptotic complexity (big-O and the rest) of methods of .NET collection classes (Dictionary<K,V>, List<T> etc...)?

I know that the C5 library's documentation includes some information about it (example), but I'm interested in standard .NET collections too... (and PowerCollections' information would also be nice).

Solution 1

MSDN Lists these:

• Dictionary<,>
• List<>
• SortedList<,> (edit: wrong link; here's the generic version)
• SortedDictionary<,>

etc. For example:

The SortedList(TKey, TValue) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary(TKey, TValue) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey, TValue).

SortedDictionary(TKey, TValue) has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList(TKey, TValue).

If the list is populated all at once from sorted data, SortedList(TKey, TValue) is faster than SortedDictionary(TKey, TValue).

Solution 2

This page summarises some of the time comlplexities for various collection types with Java, though they should be exactly the same for .NET.

I've taken the tables from that page and altered/expanded them for the .NET framework. See also the MSDN pages for SortedDictionary and SortedList, which detail the time complexities required for various operations.

---

Searching

Type of Search/Collection Types           Complexity  Comments
Linear search Array/ArrayList/LinkedList  O(N)        Unsorted data.
Binary search sorted Array/ArrayList/     O(log N)    Requires sorted data.
Search Hashtable/Dictionary<T>            O(1)        Uses hash function.
Binary search SortedDictionary/SortedKey  O(log N)    Sorting is automated.

Retrieval and Insertion

Operation         Array/ArrayList  LinkedList  SortedDictionary  SortedList
Access back       O(1)             O(1)        O(log N)          O(log N)
Access front      O(1)             O(1)        N.A.              N.A.
Access middle     O(1)             O(N)        N.A.              N.A.
Insert at back    O(1)             O(1)        O(log N)          O(N)
Insert at front   O(N)             O(1)        N.A.              N.A.
Insert in middle  O(N)             O(1)        N.A.              N.A.

Deletion should have the same complexity as insertion for the associated collection.

SortedList has a few notable peculiarities for insertion and retrieval.

Insertion (Add method):

This method is an O(n) operation for unsorted data, where n is Count. It is an O(log n) operation if the new element is added at the end of the list. If insertion causes a resize, the operation is O(n).

Retrieval (Item property):

Retrieving the value of this property is an O(log n) operation, where n is Count. Setting the property is an O(log n) operation if the key is already in the SortedList<(Of <(TKey, TValue>)>). If the key is not in the list, setting the property is an O(n) operation for unsorted data, or O(log n) if the new element is added at the end of the list. If insertion causes a resize, the operation is O(n).

Note that ArrayList is equivalent to List<T> in terms of the complexity of all operations.

---

Solution 3

I don't know in general (the other answer just posted perhaps gives you exactly what you're after) - but you can reflect this and other methods of course using ILSpy (a little awkward with FSharp code, true) and this eventually yields this function as C#:

internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
  while (true)
  {
    SetTree<a> setTree = s;
    if (setTree is SetTree<a>.SetOne)
    {
      break;
    }
    if (setTree == null)
    {
      return n;
    }
    SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
    SetTree<a> arg_23_0 = setNode.item3;
    n = setNode.item1;
    s = arg_23_0;
  }
  return ((SetTree<a>.SetOne)s).item;
  return n;
}

Okay so this is not exactly 'proper' code in C# terms - but the presence of the while(true) loop implies it can't be O(1) at least; as for what it actually is... well, my head hurts too much to find out :)

Solution 4

This page presents short notes about some key pros & cons for most .NET Collections :

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Collection	Ordering	Contiguous Storage	Direct Access	Lookup Efficiency	Manipulate Efficiency	Notes
Dictionary	Unordered	Yes	Via Key	Key: O(1)	O(1)	Best for high performance lookups.
SortedDictionary	Sorted	No	Via Key	Key: O(log n)	O(log n)	Compromise of Dictionary speed and ordering, uses binary search tree.
SortedList	Sorted	Yes	Via Key	Key: O(log n)	O(n)	Very similar to SortedDictionary, except tree is implemented in an array, so has faster lookup on preloaded data, but slower loads.
List	User has precise control over element ordering	Yes	Via Index	Index: O(1) Value: O(n)	O(n)	Best for smaller lists where direct access required and no sorting.
LinkedList	User has precise control over element ordering	No	No	Value: O(n)	O(1)	Best for lists where inserting/deleting in middle is common and no direct access required.
HashSet	Unordered	Yes	Via Key	Key: O(1)	O(1)	Unique unordered collection, like a Dictionary except key and value are same object.
SortedSet	Sorted	No	Via Key	Key: O(log n)	O(log n)	Unique sorted collection, like SortedDictionary except key and value are same object.
Stack	LIFO	Yes	Only Top	Top: O(1)	O(1)*	Essentially same as List except only process as LIFO
Queue	FIFO	Yes	Only Front	Front: O(1)	O(1)	Essentially same as List except only process as FIFO

View more solutions

Comments

[Igor Brejc]

I meant their operations, I've edited the question to make it clearer.

[Igor Brejc]

Are you sure that the complexities should be the same for .NET? I would think it's more subtle than that - for example, there's a difference between SortedDictionary, SortedList and Hashtable in .NET.

[Noldorin]

Yeah, there's no fundamental difference - the basic algorithms and data structures are going to be virtually identical. I haven't detailed SortedDictionary/SortedList, but I'll add them in now. Hashtable ought to have the same complexities as Dictionary, I believe (it's pretty much a non-generic version of it).

[Stephan Eggermont]

In this (old, deleted) quote a binary search tree is confused with a sorted array-based collection. en.wikipedia.org/wiki/Binary_search_tree

[Mike Caron]

To be fair, an array is a perfectly reasonable store for a binary tree. See: webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

[Stephan Eggermont]

Yes and no. Yes, as it is of course all mapped to main memory, which provides an array-like interface (but very much skewed to preferring access to data in the same cache line). No, as this provides not a reasonable implementation for any but the smallest (and balanced) trees. A multiway tree fits much better with current processor design

[Chris Lucian]

Note where they list the O notation. "The Dictionary<TKey, TValue> generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey, TValue> class is implemented as a hash table."

[Shog9]

FYI: merged from stackoverflow.com/questions/6313896/…

[Shog9]

FYI: merged from stackoverflow.com/questions/6313896/…

[Nathan Smiechowski]

There is no guarantee whatsoever that the underlying implementation is comparable.

[Noldorin]

No, but this is the case for the official .NET implementation.

[Larry Smith]

The link is down, which is why it's better to also quote relevant content because now people have no way to reference this possibly helpful information.

[KMR]

luckily backed up why the Internet Archive here: web.archive.org/web/20121022141414/http://geekswithblogs.net‌​/…