Dan Dinu Dan Dinu - 11 months ago 61
C# Question

What is the complexity of these Dictionary methods?

Can anyone explain what is the complexity of the following



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))

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 Source

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();