Time Complexity of std::multimap::equal_range

Question

Good afternoon, I am wondering what the time complexity of std::multimap::equal_range is? Is it Big-O(n) or BIG-0(log n). I remember reading that the time complexity of std::multimap::erase "is logarithmic plus linear time for the length of the sequence being removed." <http://frank.mtsu.edu/~csjudy/STL/Multimap.html>

Answer 1

C++03 standard, Table 69 ("Associative container requirements") in 23.1.2 says that equal_range has logarithmic complexity.

Answer 2

equal_range is an O(log n) operation returning the pair of lower_bound and upper_bound.

This means it will return an iterator range starting with the first key that is greater-than or equal-to the search key and ending with the first key that is greater than the search key.