This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

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(i) 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.