CODEWITHSUNDEEP
c#dictionarycollections
Alexander Alexander
Alexander Alexander

Reputation: 21

Dictionary<TKey, TValue> Sorted and not Sorted. Retreival time

From MSDN:

The SortedDictionary<TKey,TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary

From MSDN:

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.

My question is twofold:

  1. what is O(log n) and O(1); and
  2. what makes Dictionary (not sorted) very fast? Does it need much more memory?

Upvotes: 0

Views: 45

Answers (1)

jzarob
jzarob

Reputation: 437

O(n) is notation used to denote a weak upper bound. O(log n) means that an operation takes about log n steps to complete (it depends on the size of the input). O(1) means that the time to access is bounded by a constant, instead of the size of the input.

The Dictionary class has amortized constant access (but is not necessarily guaranteed because it might have to resize), where as the the SortedDictionary will have guaranteed access time of O(log n) because it is built from a tree.

Here's a nice intro to hash tables: hash tables

Upvotes: 2

Related Questions