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

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

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

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

 Оценка сложности последовательного алгоритма T1   = nlogn

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

Tp=(n/p)*log(n/p) + log p + log(n/p)*log p

S = o(nlogn)/o( n/p)*log(n/p) + log p + log(n/p)*log p)