Unordered Set and unordered map Q2

#1

I am unable to have a clear understanding of how the complexities are what they are. Can you please make me understand it a little bit more clearly on how the complexities are O(k) and O(logK).

Unordered Sets And Unordered Maps Quiz
#2

First go through this article https://www.geeksforgeeks.org/hash-table-vs-stl-map/

Since first implementation is a hashmap based on array of linked list. Whenever there is a collision, (different element at the same index in array) a linked list is maintained (Seperate chaining collision handling scheme). For k collisions, a k sized linked list would be formed at that index. Complexity to iterate this linked list is O(k) so answer is O(k).

Second implementation is based on a set. Set has property similar to that of stl map. It is made using self balancing tree. So its complexity is O(log k)

1 Like
#3

Thanks for the clarification.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.