O(N) Identification of Permutations

Question

This answer determines if two strings are permutations by comparing their contents. If they contain the same number of each character, they are obviously permutations. This is accomplished in O(N) time.

I don't like the answer though because it reinvents what is_permutation is designed to do. That said, is_permutation has a complexity of:

At most O(N²) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1)

So I cannot advocate the use of is_permutation where it is orders of magnitude slower than a hand-spun algorithm. But surely the implementer of the standard would not miss such an obvious improvement? So why is is_permutation O(N²)?

Answer 1

is_permutation works on almost any data type. The algorithm in your link works for data types with a small number of values only.

It's the same reason why std::sort is O(N log N) but counting sort is O(N).