Proposed resolution:

Change [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).

The complexity for minmax_element ([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).