Lecture overview -- Keyboard shortcut: 'u'  Previous page: Notes about Dictionary Classes -- Keyboard shortcut: 'p'  Next page: Non-generic Collections in C# [Section] -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home  Page 29 : 36
Object-oriented Programming in C#
Collection Classes
Time complexity overview: Dictionary classes

Assume that we work on a dictionary with n elements

OperationDictionary<K,V>SortedDictionary<K,V>SortedList<K,V>
this[key] O(1) O(log n) O(log n) or O(n)
Add(key,value) O(1) or O(n) O(log n) O(n)
Remove(key) O(1) O(log n) O(n)
ContainsKey(key) O(1) O(log n) O(log n)
ContainsValue(value)O(n) O(n) O(n)

Time complexities of important operations in the classes Dictionary<K,V>, SortedDictionary<K,V>, and SortedList<K,V>.

  • Notes

    • Add(key,value) in Dictionary<K,V>:

      • Worst case if the hashtable must be enlarged

      • Constant times indicate amortized complexity