Для анализа будем использовать следующие показатели:

• T₁ - время решения задачи на одном процессоре.
• T_p - время решения задачи на p процессорах.
• S - ускорение (speedup). Ускорение определяется из отношения: S=T₁/T_p

Оценка сложности для всех трёх алгоритмов носит схожий характер:

Сложность последовательного алгоритма T₁   = O(n)

Для  p потоков:

T_p=О(n/p)

S = О(n)/O(n/p)->p