CODEWITHSUNDEEP
dictionaryvectorbig-otime-complexity
user209306
user209306

Reputation: 89

map.find() time complexity

If I have a map:

map myMap<string,vector<int>>

What would the best,average, and worst case time complexity be to find a key, and then iterate through the vector to find a specific int?

I know the map.find() method is O(log n), but does the fact that I have to then search for an int within a vector change the time complexity?

Thanks

Upvotes: 0

Views: 1339

Answers (1)

mpontes
mpontes

Reputation: 3004

It'd help if you had stated this was C++. std::map is usually implemented as a binary tree, so that's where the O(log(n)) on the find operation comes from.

It'd be O(log(n) + m), where n is the size of the map and m is the size of (each) vector. I'm assuming that you only do one lookup and then iterate through the whole vector that corresponds to your key.

Since log(n) grows slowly, unless you have extremely small vectors, log(n) should be < m, therefore your algorithm should be O(m).

Upvotes: 0

Related Questions