Take the 2-minute tour ×

I would like to know the complexity of the following function.
I know that std::map is implemented as red-black tree and complexity of insert is O(logN).
But how can I calculate if I keep adding N items to an empty map?

void add(int N, std::map<int, int>& map) {
    map[i] = i;

Thanks in advance,

share|improve this question

3 Answers 3

up vote 2 down vote accepted

You're doing an O(log N) thing N times, so it's O(N log N).

share|improve this answer
Thanks! I think O(log0 + log1 + log2 + ... + logN). Is it equivalent to O(NlogN)? –  zorio Mar 20 '13 at 3:56
Yes, it is. Log(const value) are ignored to estimate the complexity. –  Ian Medeiros Mar 20 '13 at 4:35
@IanMedeiros this is not Log(const), it's a sum of Log(const)s - these are 2 very different things –  icepack Mar 21 '13 at 20:42
@zorio O(log1+log2+..+logN)=O(log(N!))~O(NlogN) (see en.wikipedia.org/wiki/Stirling%27s_approximation). For the first element the complexity isn't O(log0) but O(1). –  icepack Mar 21 '13 at 20:43
@JohnZwinck -1, result is correct but the analysis isn't. –  icepack Mar 22 '13 at 8:39

R-B tree is kind of balanced binary tree. The insertion operations basically finds the insert position, allocate space for the newly inserted node and adjust pointers then rebalance the R-B tree. The complexity of insertion is O(logN).

Since in your case, you first decide the complexity of certain operation, which is insert with log(N) complexity, then find out how many times the operation is used. That's why we have N(logN). O(logN) means that the order of growth of time used with respect to number of elements in the container is at most order of logN. It does not really mean that the actual time used is logN.

If your application is time critic, you may consider use unordered_map since insertion time complexity is constant. You are mapping from int to int, so it should be perfectly fine to use unordered_map in this case.

BTW: in your formula, log0 is not defined, when there is no elements to insert, you don't carry the insertion operation.

share|improve this answer
Thanks! Ah, right. log 0 is not defined. –  zorio Mar 20 '13 at 8:56

You're asking a reasonable question.

When inserting N items into a tree that started out empty, you're starting from log(0) and progressing to log(N). That means your overall average is really log(N/2) instead of log(N).

In the case of a logarithm, that doesn't really make a difference though -- the overall complexity is still logarithmic. What you've done is in effect changed the base of the logarithm.

share|improve this answer
Make sense. Thanks! –  zorio Mar 20 '13 at 8:56

Your Answer


