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
#include
#include

bool ArraysPermute(int  array1[],int size1, int  array2[], int size2)
{       
       if( size1  != size2)           
           return false;
       else
       {        
           std::set first_set(array1, array1+size1);
           std::set second_set(array2, array2+size2);

           std::pair::iterator,std::set::iterator> 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<< " Arrays are permutation of each other\n"; 
    else
        std::cout<< " 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 first_set(array1, array1+size1);
       std::set second_set(array2, array2+size2);

       std::pair::iterator,std::set::iterator> 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 first_set(array1, array1 + size1);
std::set second_set(array2, array2 + size2);

std::pair::iterator, std::set::iterator> 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]

StackExchange Code Review Q#84873, answer score: 5