4162. Worst time complexity of non-parallel versions of nth_element is underspecified

Section: 26.8.3 [alg.nth.element] Status: New Submitter: Jiang An Opened: 2024-09-29 Last modified: 2024-10-09

Priority: 3

View all other issues in [alg.nth.element].

View all issues with New status.

Discussion:

Currently, 26.8.3 [alg.nth.element] doesn't specify the worst time complexity for nth_element without ExecutionPolicy parameter, which seemingly allows a complexity that is 𝒪(N2) 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.

[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."

Proposed resolution:

This wording is relative to N4988.

1. Modify 26.8.3 [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.