Доказательство быстродействия Quick Sort.

[BanmaN]

Одно доказательство мне ясно: вычисление математического ожидагия при помощи реккуррентного соотношения. А именно заметить, что $k$-ый по макс. элемент будет выбран ровно с вероятностью $1/n$. Откуда и получить (T(n) - случайная величина, характеризующая скорость выполнения алгоритма) : $E[T(n)] = 2/n \cdot (E[T(2)]+E[T(3)]+...+E[T(n-1)]) + O(n) $.

А вот второе (оба доказательства приведены в книге Кормен "Алгоритмы помтроение и анализ") неясно : там рассматриваются множеста $Z_{i,j} = {z_{i}, z_{i+1}, ... , z_{j}}$ и говориться, что
1) два элемента сравниваются не более 1-го раза - это очевидно.
2) для того, чтобы сравнились $z_{i}, z_{j}$ необходимо и достаточно, чтобы из всего множества $Z_{i,j}$ раздел проходил именно по $i$-ому или $j$-ому элементу. - Это тоже ясно.

Но вот вопрос: ведь при операции разделения у нас меняется порядок и мы не сможем ничего говорить про какиу-то индексы $i, j$, а они говорят, мол, так получается, что математическое ожидание случайной величины равно сумме этих вероятностей, а оно равно сумме обратных величин от мощностей всех этих множеств, а там всё ясно. Ряд-то там получается несложный, но сам момент почему суммируется по всем $i, j$ - неясен.

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

Заранее спасибо!

[BanmaN]

Я сам понял!
Там просто имелось ввиду не то, что идут в ряду между ними, а в упорядоченном множестве элементов. А тойда и действительно необходимо и достаточно, чтобы разделение проходило по крайним.