Изменения
→Среднее время работы
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.
Заметим, что сравнеие сравнение каждой пары элементов происходит не больше одного раза, так как элемент сравнивается с опорным, а опорный элемент после разбиения больше не будет участвовать в сравнении.
Поскольку каждая пара элементов срановается сравнивается не более одного раза, полное количество сравнений выражается как
<tex>X = \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} X_{ij}</tex>, где <tex>X_{ij} = 1</tex> если произошло сравнение <tex>z_i</tex> и <tex>z_j</tex> и <tex>X_{ij} = 0</tex>, если сравнения не произошло.
