Many collection classes offer the same functionality as others; for example, SortedList offers nearly the same features as SortedDictionary. However, often there’s a big difference in performance. Whereas one collection consumes less memory, the other collection class is faster with retrieval of elements. In the MSDN documentation, you often find performance hints with methods of the collection giving you information about the time the operation represents in big·O notation:
0(1) means that the time this operation needs is constant no matter how many items are in the collection. For example, the ArrayList has an Add() method with 0(1) behavior. No matter how many element are In the list, It always takes the some time when adding a new element to the end of the list. The count. property gives the number of items, 10 it is easy to find the end of the list.
O(n) means that for every element in the collection the same amount of additional time is needed. The Add() method of ArrayList can be an O(n) operation if a reallocation of the collection is required. Changing the capacity causes the copying of the list, and the time for the copy increases linearly with every element.
O(log n) means that the time needed for the operation increases with every element in the collection. But the increase of time for every element is not linear but logarithmic. SortedDictionary<TKey, TValue> has O(log n) behavior for inserting operations inside the collection; SortedList<TKey, TValue> has O(n) behavior for the same functionality. Here, SortedDictionary<TKey, TValue> is a lot faster because it is more efficient to insert elements into a tree structure than into a list.
The following table lists collection classes and their performance for different actions such as adding, inserting, and removing items. Using this table you can select the best collection class for the purpose of your use. The left column lists the collection class. The Add column gives timing information about adding items to the collection. The List<T> and the HashSet<T> classes define Addmethods to add items to the collection. With other collection classes, there’s a different method to add elements to the collection; for example, the Stack<T> class defines a Push () method, and the Queue<T>class defines an Enqueue () method. Youcan find this information in the table as well.
If there are multiple big-O values in a cell the reason is that if a collection needs to be resized, resizing takes a while. For example, with the List<T> class, adding items needs 0(1). If the capacity of the collection is not large enough and the collection needs to be resized, the resize requires O(n) time. The larger the collection is, the longer the resize operation takes. It’s best to avoid resizes by setting the capacity of the collection to a value that can hold all elements.
If the cell content is na, this means that this operation is not applicable with this collection type .