user2600312 user2600312 - 5 months ago 50
C++ Question

Big O when stacking containers

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: 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 this map?


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.