Можно решить так: из массива M находить-и-удалять элементы массива N по одному. Если какой-либо элемент N не найден в M ИЛИ дойдя до последнего элемента массива N в массиве M останется хотя бы один элемент — значит они не являются перестановкой.
На простом неотсортированном массиве M сложность поиска элемента O(M) а удаления O(1) + мы проходим по массиву N, тогда сложность алгоритма будет O(N*M).
Однако, при смене контейнера, к примеру, на хешированный словарь, можно сократить сложность поиска до O(logM), тогда и общая сложность алгоритма упадет.
Что скажете? Комментарии? Замечания? Предложения?