What is the time complexity of inserting an element into a C++ multiset ?
Tripura Public Service Commission - 2026,
Answer: C
Inserting into a std::multiset takes O(log n) time.
A C++ multiset keeps its elements in sorted order and is implemented as a self-balancing binary search tree (in practice a red-black tree). An insertion walks down the tree to find the position and then rebalances, and both steps are bounded by the tree's height, which is O(log n).
O(1) average insertion belongs to the hash-based unordered_multiset. O(n) would be insertion into a sorted array or list, where elements must be shifted or scanned. O(n log n) is the cost of inserting n elements, or of sorting, not of one insertion.
Please log in or register to report this question.