Изменения

На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за <tex>O(N)</tex>. Вероятность, что мы выбрали элемент "удачно" составляет <tex>1 / K</tex>. Тогда, в среднем, мы будем делать <tex>K</tex> шаговпроверок. Итоговая сложность <tex>O(N \cdot K)</tex>.