Check whether given a pair of arrays are permutation of each other
Complexity

You suggest that the performance is \$O(n)\$, but it is not. It is \$O(n \log{n})\$ because the set constructor is a binary-tree building algorithm that has an additional log(n) operations for each value.

Style

While your code is all neat, and well laid out, the variable names are good, etc., there are two issues I see with unnecessary else-condiditions on if-statements, and un-braced 1-liners. Additionally, white-space around punctuation and operators is useful for readability. This code:


  if( size1  != size2)           
       return false;
   else
   {        
       std::set&lt;int&gt; first_set(array1, array1+size1);
       std::set&lt;int&gt; second_set(array2, array2+size2);

       std::pair&lt;std::set&lt;int&gt;::iterator,std::set&lt;int&gt;::iterator&gt; myPair=std::mismatch(first_set.begin(),first_set.end(),second_set.begin());

       if( *myPair.first != *myPair.second)

            return false;
        else
            return true;
   }



should be written:

if( size1 != size2)
{
    return false;
}
std::set&lt;int&gt; first_set(array1, array1 + size1);
std::set&lt;int&gt; second_set(array2, array2 + size2);

std::pair&lt;std::set&lt;int&gt;::iterator, std::set&lt;int&gt;::iterator&gt; myPair   
   = std::mismatch(first_set.begin(), first_set.end(), second_set.begin());

return *myPair.first == *myPair.second;


Bugs

The set construct keeps just a single entry for all instances of a given value. Thus, for example, given the input [1,2,3,4,4,4,4] it will have just 4 entries.

This leads to bugs in your code when there are duplicates. For example, your code will identify the following two input arrays as being permutations of each other:

[1,2,3,4,5,5,5]
[1,1,1,2,3,4,5]