Why is worst case of is_permutation O(n^2)?

user_9037005 0
Viewed 105

The C++ docs say that the worst case time complexity for is_permutation is O(N^2):

At most O(N^2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first1, last1). However if ForwardIt1 and ForwardIt2 meet the requirements of LegacyRandomAccessIterator and std::distance(first1, last1) != std::distance(first2, last2) no applications of the predicate are made.

However, IMO it should be O(NlogN) in the worst case - can we not just sort both the sequences in O(NlogN) and then just compare them? What am I missing?

permutation algorithm c++
1 Answers

is_permutation doesn't require the ranges to be sortable. It only uses the bool-valued comparison predicate.

Furthermore, the ranges are immutable, so even if they could be sorted, the sorting would imply creation of an index on one of the ranges. That would add O(N) memory cost to the O(NlogN) cost of index generation.

user_13296520
Related