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

T1 - время решения задачи на одном процессоре.

Tp - время решения задачи на p процессорах.

S - ускорение (speedup). Ускорение определяется из отношения: S=T1/Tp

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

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

Tp=О(n/p)

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