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

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

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

Можно проверять, например, каждую n-ную итерацию. Тогда асимптотика останется — правда константа вырастет.