What is time and space complexity of Dictionary?

Question

Let's assume I have data of size N (i.e.N elements) and the dictionary was created with capacity N. What is the complexity of:

• space -- of entire dictionary
• time -- adding entry to dictionary

MS revealed only that entry retrieval is close to O(1). But what about the rest?

Answer 1

The time complexity of adding a new entry is documented under Dictionary<T>.Add():

If Count is less than the capacity, this method approaches an O(1) operation. If the capacity must be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

Answer 2

What is the complexity of space -- of entire dictionary

Dictionary uses associative array data structure that is of O(N) space complexity.

Msdn says: "the Dictionary class is implemented as a hash table". And hash table uses associative arrays in turn.

What is the complexity of time -- adding entry to dictionary

A single add takes amortized O(1) time. In most cases it is O(1), it changes to O(N) when the underlying data structure needs to grow or shrink. As the later only happens infrequently, people use the word "amortized".

Answer 3

It is not formally documented, but widely stated (and visible via disassembly) that the underlying storage is an array of name-value pairs. Thus space complexity is O(n).

As it is not part of the specification this could, in theory, change; but in practice is highly unlikely to because it would change the performance of the various operations (eg. enumeration) which could be visible.