Alguém pode explicar qual é a complexidade do seguinteDictionary métodos

ContainsKey(key)
Add(key,value);

Estou tentando descobrir a complexidade de um método que escrevi:

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

Assumi que os 2 métodos de dicionário são de complexidade em log (n) onden é o número de chaves no dicionário. Isso está correto?