Proposed resolution:

Change [alg.lex.comparison] complexity to:

At most 2*min((last1 - first1), (last2 - first2)) applications of the corresponding comparison.

Change the example at the end of paragraph 3 to read:

[Example:

    for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2) {
      if (*first1 < *first2) return true;
      if (*first2 < *first1) return false;
    }
    return first1 == last1 && first2 != last2;
   
--end example]

The lexicographical_compare complexity is specified as:

     "At most min((last1 - first1), (last2 - first2)) applications of the corresponding comparison."

The best I can do is twice that expensive.

Nicolai Josuttis comments in lib-6862: You mean, to check for equality you have to check both < and >? Yes, IMO you are right! (and Matt states this complexity in his book)