Чтобы понять анализ в цитированной вами книге, вам нужно понять некоторые понятия из теории вероятностей.
Мы хотим определить среднее число сравнений, выполненных быстрой сортировкой.
Определим несколько случайных величин. X_ij = 1, если сравниваются z_i и z_j, и 0 в противном случае. X - случайная величина для общего числа проведенных сравнений. Таким образом, X = сумма по i и j для X_ij.
E [X] - это ожидаемое значение для X, то есть значение "в среднем". Ожидание является линейным, поэтому ожидание суммы равно сумме ожиданий. Так в книге делается вывод, что среднее число сравнений равно сумме по i и j из E [X_ij]. Поскольку X_ij равен 0 или 1, его ожидаемое значение совпадает с вероятностью проведения сравнения между z_i и z_j.
Если после этого у вас все еще есть проблемы, вам нужно прочитатьвероятность, случайные величины и ожидаемые значения.