What is the complexity of these Dictionary methods?

Question

Can anyone explain what is the complexity of the following Dictionary methods?

ContainsKey(key) Add(key,value); 

I'm trying to figure out the complexity of a method I wrote:

public void DistinctWords(String s) {     Dictionary<string,string> d = new Dictionary<string,string>();     String[] splitted = s.split(" ");     foreach ( String ss in splitted)     {          if (!d.containskey(ss))             d.add(ss,null);     }  } 

I assumed that the 2 dictionary methods are of log(n) complexity where n is the number of keys in the dictionary. Is this correct?

Answer 1

It's written in the documentation for Dictionary...

The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

And for the Add function:

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

Both methods have constant complexity:

• ContainsKey(key) - O(1)
• Add(key,value) - O(1)