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

### 715. `minmax_element` complexity is too lax

Section: 27.8.9 [alg.min.max] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.min.max].

View all issues with CD1 status.

Discussion:

The complexity for `minmax_element` (27.8.9 [alg.min.max] par 16) says "At most `max(2 * (last - first ) - 2, 0)` applications of the corresponding comparisons", i.e. the worst case complexity is no better than calling `min_element` and `max_element` separately. This is gratuitously inefficient. There is a well known technique that does better: see section 9.1 of CLRS (Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein).

Proposed resolution:

Change 27.8.9 [alg.min.max] to:

>     template<class ForwardIterator>
>       pair<ForwardIterator, ForwardIterator>
>         minmax_element(ForwardIterator first , ForwardIterator last);
>     template<class ForwardIterator, class Compare>
>       pair<ForwardIterator, ForwardIterator>
>         minmax_element(ForwardIterator first , ForwardIterator last , Compare comp);

> > Returns: `make_pair(m, M)`, where `m` is `min_element(first, last)` or `min_element(first, last, comp)` the first iterator in `[first, last)` such that no iterator in the range refers to a smaller element, and where `M` is `max_element(first, last)` or `max_element(first, last, comp)` the last iterator in `[first, last)` such that no iterator in the range refers to a larger element.

> > Complexity: At most `max(2 * (last - first ) - 2, 0)` `max(⌊(3/2) (N-1)⌋, 0)` applications of the corresponding comparisons predicate, where `N` is `distance(first, last)`.