Proposed resolution:

This wording is relative to N3936.

1. In [sort.heap] p3 the Standard states:

   template<class RandomAccessIterator>
     void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
   template<class RandomAccessIterator, class Compare>
     void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp);
   

   […]

   -3- Complexity: At most 2N log(N) comparisons (where N == last - first).

[ 2017-03-04, Kona ]

Move to Tentatively Ready. STL may write a paper (with Thomas & Robert) offering guidance about Big-O notation vs. exact requirements.

[ 2015-05-06 Lenexa ]

STL: I dislike exact complexity requirements, they prevent one or two extra checks in debug mode. Would it be better to say O(N log(N)) not at most?

[ 2015-02 Cologne ]

Marshall will research the maths and report back in Lenexa.

While creating complexity tests for the GNU libstdc++ implementation I stumbled across a surprising requirement for the std::sort_heap algorithm.

In [sort.heap] p3 the Standard states:

Complexity: At most N log(N) comparisons (where N == last - first).

As stated on the libstdc++ mailing list by Marc Glisse sort_heap can be implemented by N calls to pop_heap. As max number of comparisons of pop_heap is 2 * log(N) then sort_heap max limit should be 2 * log(1) + 2 * log(2) + .... + 2 * log(N) that is to say 2 * log(N!). In terms of log(N) we can also consider that this limit is also cap by 2 * N * log(N) which is surely what the Standard wanted to set as a limit.

This is why I would like to propose to replace paragraph 3 by:

Complexity: At most 2N log(N) comparisons (where N == last - first).