What is the time complexity of inserting an element into a C++ multiset?

Concept

A container implemented as a self-balancing binary search tree (for example a red-black tree) keeps the tree height proportional to log n, where n is the number of stored elements. Because every standard operation on such a tree — search, insertion, and deletion — works by walking from the root down to a single leaf, and the walk length is bounded by the tree height, every one of these operations runs in O(log n) time, regardless of the order in which elements were inserted.

Application

The C++ Standard Library specifies std::multiset (and the related std::set, std::map, and std::multimap) as ordered associative containers, and its insert operation is specified with logarithmic complexity — O(log(size())) for inserting a single element with no positional hint. Concretely, here is what happens when inserting into a multiset that already holds the sorted values {10, 20, 30, 40} (stored as a balanced tree, height ≈ log₂(4) ≈ 2):

1. Start at the root of the internal tree and compare the new value, 25, against it (e.g. root = 20): 25 > 20, so move to the right subtree.

2. At the next node (e.g. 30), compare again: 25 < 30, so move to the left subtree.

3. An empty spot is reached after this constant number of comparisons — one per level of the tree, and the number of levels is O(log n) — so the new node for 25 is attached there.

4. If the tree’s balance property is violated by the insertion, recoloring may propagate up through at most O(log n) ancestor levels, with a constant number of rotations applied at the end to restore balance; this rebalancing cost is itself bounded by the tree height, so it stays within the same O(log n) bound.

Every comparison in this walk eliminates roughly one level of the tree rather than one element, so the total work is proportional to the tree’s height, O(log n), not to the total element count n.

Cross-check

This matches the general rule for ordered (tree-based) associative containers: std::set and std::map, built the same way, also give O(log n) insertion, search, and deletion. It contrasts with std::unordered_multiset, a hash-based container, whose insertion is O(1) on average (not because of a tree walk, but because a hash function locates a bucket directly). It also contrasts with inserting into an unsorted flat structure such as a std::vector at an arbitrary sorted position, which needs O(n) work to shift existing elements — confirming that the tree-based, height-bounded walk described above is what produces the logarithmic bound for a multiset.