Discussion
What is the time complexity of inserting an element into a C++ multiset ?
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.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development