Одно доказательство мне ясно: вычисление математического ожидагия при помощи реккуррентного соотношения. А именно заметить, что

-ый по макс. элемент будет выбран ровно с вероятностью

. Откуда и получить (T(n) - случайная величина, характеризующая скорость выполнения алгоритма) :
![$E[T(n)] = 2/n \cdot (E[T(2)]+E[T(3)]+...+E[T(n-1)]) + O(n) $ $E[T(n)] = 2/n \cdot (E[T(2)]+E[T(3)]+...+E[T(n-1)]) + O(n) $](https://dxdy-03.korotkov.co.uk/f/6/4/f/64f5d2ca47188fdd88e2da4577c184b682.png)
.
А вот второе (оба доказательства приведены в книге Кормен "Алгоритмы помтроение и анализ") неясно : там рассматриваются множеста

и говориться, что
1) два элемента сравниваются не более 1-го раза - это очевидно.
2) для того, чтобы сравнились

необходимо и достаточно, чтобы из всего множества

раздел проходил именно по

-ому или

-ому элементу. - Это тоже ясно.
Но вот вопрос: ведь при операции разделения у нас меняется порядок и мы не сможем ничего говорить про какиу-то индексы

, а они говорят, мол, так получается, что математическое ожидание случайной величины равно сумме этих вероятностей, а оно равно сумме обратных величин от мощностей всех этих множеств, а там всё ясно. Ряд-то там получается несложный, но сам момент почему суммируется по всем

- неясен.
Мне, наверное, что-то идеологически неясно. Объясните, пожалуйста.
Заранее спасибо!