3

On https://en.cppreference.com/w/cpp/container/priority_queue/emplace, it shows:

Logarithmic number of comparisons plus the complexity of Container::emplace_back.

But from Argument for O(1) average-case complexity of heap insertion, Heap vs Binary Search Tree (BST), and other resources, the average complexity of insertion into a heap is constant, with worst case logarithmic complexity. On cppreference, it typically shows the average case complexity along with the worst case complexity for a given function. In this particular cppreference link, it does not differentiate whether this is average or worst case complexity, but I think it may be referring to the "average" case complexity as generally that is what is presented when people talk about complexity. If that's the case, how is it that the STL implementation of this function is logarithmic on average?

user5965026
  • 465
  • 5
  • 16

2 Answers2

2

cppreference is a user-curated wiki. It's possible for it to be missing documentation or flat out wrong (which happens from time to time). Usually any inconsistency is because they're trying to make it understandable by regular developers, though. The standard always has the final say (although even it has ambiguity and contradictions from time to time).

That said, here's what the standard has to say on listed time complexities, per [structure.specifications]

Complexity requirements specified in the library clauses are upper bounds, and implementations that provide better complexity guarantees satisfy the requirements.

The worst case time complexity is always given, and the standard will point out places where average or amortized complexity is better, for example in the description for emplace in unordered associative containers:

Average case O(1), worst case O(a_eq. size()).

AndyG
  • 39,700
  • 8
  • 109
  • 143
0

When the standard is specifying complexity, it is worst-case unless otherwise specified, and is often not big-O, instead an exact limit of a specified operation.

E.g. "At most last - first applications of the predicate" for std::find_if

Caleth
  • 52,200
  • 2
  • 44
  • 75