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

А>Вообще-то сойдется на бесконечности, это элементарно доказывается.

Что означает "на бесконечности" в контексте обсуждения сложности худшего случая?

А>А вот критерия остановки нет потому что у бесконечных итеративных алгоритмов его в принципе не бывает

Критерий остановки — массив отсортирован, не?

А>что, однако, совcем не мешает оценивать трудоемкость

У этого алогритма нет оценки трудоёмкости в худшем случае.

А>зато замечательно ставит студиозусов в тупик.

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