Здравствуйте, Константин, Вы писали:

К>Здравствуйте, denisko, Вы писали:

D>>Здравствуйте, Don Reba, Вы писали:


DR>>>Проверка отсортированнасти массива — O(n); вероятность того, что массив отсортирован — 1/n!. Средняя сложность — O(n*n!).
D>>Да ладно, через O(n^4) должен останавливаться в среднем.

К>Думаю, даже O(n^2 * log(n)).
Добавь еще то, что на каждом цикле придется проверять, отсортирован ли массив тогда получится O(n^3 logN), что звучит очень разумно.