I am just starting to learn about the time complexities and I just want to make sure I am getting this right.
if we have a unordered_map<string, set<int>>
note that organized as hash tables that never allow the load factor to exceed some constant.
Lets say string are business names and in set<int> we have employee ID's, if we want to print all employee id's in some given business, what will be the time complexity. And here is my logic, please let me know if I am heading in right direction.
My logic is this, since hash table load constant will not exceed some constant, finding a particular business will be constant time operation so O(1). Printing all names in a list is basically BST in order traversal so it will be O(N) on average. hence overall it will be O(1)+O(N) which is basically O(N). is this correct?
Well the important thing to understand is how you're counting the complexity.
Let's say you have N entries in the first container and the std::set<int> contains M elements. With a container that allows fast search, the first part is O(1) then printing is O(M).
However, if you were using something like a std::vector the complexity would be O(N)+O(M) (because the search is slow). For a regular map, it would be O(logN)+O(M).
Since N and M are (without more data) uncorrelated, you can't put them together in the O expressions.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments