Big O when stacking containers

Question

I use a std::map which is implemented as red-black tree with time complexity of O(log(N)) for access (according to this site: http://bigocheatsheet.com/). How do I calculate the big O if I stack these containers.

For example map<int, map<int, int>>. What is the big O for accessing the innermost map?

Answer 1

You just need to sum the complexities in this case,

map<int, map<int, int>> data;
const auto& lookup = data[5]; // here you spend O(logn)
int value lookup2 = lookup[3]; // here you spend O(logn)

So it's O(logn) + O(logn) = O(klogn) = O(logn).

This would be O(logn) also in case of map<int, map<int, map<int, map<int, .. and so on because the amount of nested levels doesn't depend on N but they are always constant.