Check whether given a pair of arrays are permutation of each other Does this implementation guarantee execution of \$O(n)\$ time?  What is the additional space utilization for this implementation by excluding the original array size? Is it \$O(1)\$?

#include&lt;iostream&gt;
#include&lt;set&gt;
#include&lt;algorithm&gt;


bool ArraysPermute(int  array1[],int size1, int  array2[], int size2)
{       
       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;
       }
}


int main()
{     
    int array1[] ={1,2,3,5};
    int array2[]={1,2,4,3};

    if(ArraysPermute(array1,sizeof(array1)/sizeof(int), array2, sizeof(array2)/sizeof(int)))
        std::cout&lt;&lt; " Arrays are permutation of each other\n"; 
    else
        std::cout&lt;&lt; " Arrays are not permutation of each other\n";

    return 0;
}
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]