Big O when stacking containers

Question

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

For example map<int, map<int, int>>. What is big O to access the innermost map?

Answer 1

You just need to summarize the difficulties 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 this is O (logn) + O (logn) = O (klogn) = O (logn).

It will be O (logn) also in the case map<int, map<int, map<int, map<int, ..and so on, because the number of nested levels is independent of N, but they are always constant.

Answer 2

. map<int, map<int, int>> m, m[4][2] - . : O(log M + log N) = O(log MN) M - , N - .

, .

Answer 3

O(Log(N))

, , , , O (log (N)) . , O(2*log(N)), , O(Log(N)).

Answer 4

, O (log (N)).

, O (log (N)), "" , O (log (N)) , O (2 * log (N )), O (log (N)).