На этой лекции ознакомимся с принципом Яо, который гласит, что ожидаемое время работы рандомизированного алгоритма в худшем случае не меньше, чем ожидаемое время работы наилучшего детерминированного алгоритма на наихудшем распределении на входных данных. Иными словами, для доказательства нижнней оценки трудоёмкости алгоритмов Лас Вегас достаточно найти хотя бы одно распределение случайных входов, на котором все детерминированные алгоритмы в среднем плохо работают. Мы этот принцип используем для доказательства нижних оценок трудоёмкости рандомизированных алгоритмов для упорядочивания массива.