
O(1) = constant time
O(log n) = time proportional to the log of the number of elements in the collection
O(n) = time proportional to the number of elements in the collection
Some collections are better for smaller collections, but don't scale to larger ones. The List, LinkedList, SortedList, Queue and Stack classes are better for smaller collections than the Dictionary, Hashtable and SortedDictionary classes.
3 comments:
useful, thanks
I think LinkedList has complexity to remove element O(1) and NOT O(n).
See MSDN (http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx):
LinkedList<(Of <(T>)>) provides separate nodes of type LinkedListNode<(Of <(T>)>), so insertion and removal are O(1) operations.
@Anonymous
LinkedList removal is only O(1) when you already know which LinkedListNode contains the value (T) that you want to remove.
For direct comparison to the other collections I think the O(n) overload is more fitting.
Post a Comment