Menu
For set, multiset, map, multimap the time complexity for insertion, deletion and retrieving information is O(logn) as they follow the balance binary tree to structure the data.
HashMap has complexity of O(1) for insertion and lookup. HashMap allows one null key and multiple null values. HashMap does not maintain any order.
Space Complexity of hashmap in big-O notation is O(n) where n is the number of entries. Remember that, big-O notation depicts the order of growth with the number of input, it doesn't reflect the exact numerical space an algorithm takes.
The data structure of map and set are both red-black tree, so the space complexity of map is usually O(n) , but it depends on the real-world cases (see: space complexity of a map).
These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times:
Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
These are implemented using hash tables. They have the following runtimes:
Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case
If you use a proper hash function, you'll almost never see the worst case behavior, but it is something to keep in mind — see Denial of Service via Algorithmic Complexity Attacks by Crosby and Wallach for an example of that.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With