Dan Dinu Dan Dinu - 1 month ago 10
C# Question

What is the complexity of these Dictionary methods?

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

This routine, as a whole, is, effectively, O(m) time complexity, with m being the number of strings in your search.

This is because Dictionary.Contains and Dictionary.Add are both (normally) O(1) operations.

(It's slightly more complicated than that, as Dictionary.Add can be O(n) for n items in the Dictionary, but only when the dictionary capacity is small. As such, if you construct your dictionary with a large enough capacity up front, it would be O(m) for m string entries.)

That being said, if you're only using the Dictionary for existence checking, you could use a HashSet<string>. This would allow you to write:

  public void DistinctWords(String s)
  {
     HashSet<string> hash = new HashSet<string>(s.Split(' '));

     // Use hash here...

As your dictionary is a local variable, and not stored (at least in your code), you could also use LINQ:

 var distinctWords = s.Split(' ').Distinct();