Proposed resolution:

This wording is relative to N4988.

1. Modify [alg.nth.element] as indicated:

   template<class RandomAccessIterator>
     constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                                RandomAccessIterator last);
   template<class ExecutionPolicy, class RandomAccessIterator>
     void nth_element(ExecutionPolicy&& exec,
                      RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last);
   template<class RandomAccessIterator, class Compare>
     constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                                RandomAccessIterator last, Compare comp);
   template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
     void nth_element(ExecutionPolicy&& exec,
                      RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last, Compare comp);
   template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
            class Proj = identity>
     requires sortable<I, Comp, Proj>
     constexpr I
       ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
   

   […]

   -5- Complexity: For the overloads with no ExecutionPolicy, linear on average. For the overloads with an ExecutionPolicy, 𝒪(N) applications of the predicate, and 𝒪(N log N) swaps, where N = last - first. For the overloads with no ExecutionPolicy, 𝒪(N) on average.

[ 2024-10-09; Reflector poll ]

Set priority to 3 after reflector poll.

"This seems to require changes to implementations for them to meet this complexity guarantee."

Currently, [alg.nth.element] doesn't specify the worst time complexity for nth_element without ExecutionPolicy parameter, which seemingly allows a complexity that is 𝒪(N²) or even worse. Presumably we should make the worst time complexity consistent between parallel and non-parallel versions. For sort, LWG 713 already strengthened complexity requirements.