Is_permutation() on sequence containers in O(n) complexity - follow-up
I would initially agree that the complexity of your solution is O(n), though, there are extreme cases where the performance of your count_frequency could be greater - unordered_map.emplace() is 'average case constant time, worst case linear', I don't believe a worst-case situation would happen for you.

Note that you have a very complicated equality-check comparing your two frequency-maps.... you have:


if( std::distance( first1, last1 ) != std::distance( first2, last2 ) )
{
    return false;  
}
std::unordered_map&lt; int, int &gt; first_map = count_frequency( first1, last1 );        
std::unordered_map&lt; int, int &gt; second_map = count_frequency( first2, last2 );

std::pair&lt;std::unordered_map&lt; int, int &gt;::iterator,std::unordered_map&lt; int, int &gt;::iterator &gt; myPair=
    std::mismatch( std::begin( first_map ), std::end( first_map ), std::begin( second_map ), 
    []( std::pair&lt; const int, int &gt;&amp; seed1, std::pair&lt; const int, int &gt; &amp; seed2) 
    { return seed1.second == seed2.second; }
    );

return  myPair.first == first_map.end() &amp;&amp; myPair.second == second_map.end();



as far as I can tell, the size-check is redundant, and the rest can be simply:

template &lt; typename T1, typename T2 &gt;
bool is_permutation( const T1 first1, const T1 last1, const T2 first2, const T2 last2 )
{   
    return count_frequency( first1, last1 ) == count_frequency( first2, last2 );
}


I put your code in this ideone, and the replacement code in this ideone here.