Изменения
→Среднее время работы
{{
Лемма
|statement=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Тогда время Время работы алгоритма быстрой сортировки равно <tex>O(n \log n)</tex>.|proof=Пусть Х {{---}} полное количество сравнений элементов с опорным за время работы сортировки. Нам необходимо вычислить полное количество сравнений.
Переименуем элементы массива как <tex>z_1...z_n</tex>, где <tex>z_i</tex> наименьший по порядку элемент.
Также введем множество <tex>Z_{ij} = \{z_i, z_{i+1}...z_j\}</tex>.
