Complexity: O(n), where n is the number of key-value pairs in the dictionary.
As shown above, the removeValue(forKey key: Key) time complexity is O(n) not O(1).Why?
Why is the time complexity of a dictionary O(n) not O(1)
Viewed 368
2 Answers
Because of the value semantics of Dictionary. Removing a key-value pair potentially requires duplicating the data, making it a O(N) operation.
If you take a look at the source Code of removeValue() you can see that it uses the ensureUnique() function, which creates a copy of the hashmap, if the item is not unique and therefore has Complexity of O(n)
Related