




Нетрудно видеть, что при увеличении n ускорение стремится к p, а
эффективность к единице. В вышеуказанных формулах за время работы
последовательной быстрой сортировки мы взяли среднее время ее работы. То же
самое касается алгоритма поиска медианы (среднее время работы данного алгоритма
- линейное).