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.