user2600312 user2600312 - 1 month ago 14
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: 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 this map?

Answer

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.

Comments