Эффективность параллельного алгоритма сортировки n элементов на p процессорах с помощью сетей нечетно-четного слияния Бэтчера в предположении нулевой латентности и нулевого времени на передачу данных равна:
Во сколько раз в среднем сократится объем передаваемых данных при использовании алгоритма предварительного анализа числа элементов, передать которые необходимо для выполнения одной операции компаратора слияния:
Алгоритму сортировки слиянием в наихудшем случае наиболее точно соответствует оценка числа операций:
Алгоритму быстрой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:
Алгоритму пузырьковой сортировки в наихудшем случае наиболее точно соответствует оценка числа операций:
С помощью алгоритма сдваивания можно найти сумму элементов массива:
Ускорение при использование на p процессорах алгоритма прогонки для решения трехдиагональных систем из N линейных уравнений снижается за счет:
