Rationale:

The LWG considered just saying O(log n) for all three, but decided that threw away too much valuable information. The fact that lower_bound is twice as fast as equal_range is important. However, it's better to allow an arbitrary additive constant than to specify an exact count. An exact count would have to involve floor or ceil. It would be too easy to get this wrong, and don't provide any substantial value for users.